Safecracker

=== Op tech briefing, 2002/11/02 06:42 CST ===

"The item is locked in a Klein safe behind a painting on the second floor of the library. Klein safes are extremely rare; most of them, along with Klein and his factory, were destroyed in World War II. Fortunately, old Brumbaugh from research knew Klein's secrets and wrote them down before he died.

A Klein safe has two distinguishing features: a combination lock that uses letters instead of numbers, and an engraved quotation on the door. A Klein quotation always contains between five and twelve distinct uppercase letters, usually at the beginning of sentences, and mentions one or more numbers. Five of those uppercase letters form the combination that opens the safe. By combining the digits of all the numbers in the appropriate way, you obtain a numeric target. (The details of constructing the target number are classified.)

To find the combination you must choose five letters $v$, $w$, $x$, $y$, and $z$ that satisfy the equation below, where each letter is replaced by its ordinal position in the alphabet ($A=1$, $B=2$, ..., $Z=26$). The combination is then the string $vwxyz$:

$$v - w^2 + x^3 - y^4 + z^5 = T$$

Here $T$ is the target. If more than one combination satisfies the equation, the answer is the one that is lexicographically greatest, i.e. the one that would appear last in a dictionary.

For example, with target $T = 1$ and the letter set ABCDEFGHIJKL, one solution is FIECB, since $6 - 9^2 + 5^3 - 3^4 + 2^5 = 1$. Several combinations work for this target, and the lexicographically greatest of them, which is the answer, is LKEBA."

=== Op tech directive, computer division, 2002/11/02 12:30 CST ===

Write a program that finds Klein combinations for field deployment.

Each line of input contains a positive integer target $T$ (less than twelve million), a single space, and then between five and twelve distinct uppercase letters. The final line contains a target of $0$ followed by the letters END; this line marks the end of the input and is not processed.

For each input line other than the terminating END line, print the Klein combination on its own line, or print no solution if no valid combination exists.