Problem H
Hasty Hash

Hubert the dastardly villain is at it again. In order to foil his evil plot (to take over the world, of course—the details are unimportant), you need to use his credentials to log into his doomsday device and cancel the countdown. (Of course, all doomsday devices these days are IoT-enabled and come with a web-based administrative console.)

Fortunately for you (and the world), Hubert knows far less about security than he does about plotting world domination. After taking him out for drinks and asking a few leading questions, you now know that his password is a string of exactly $5$ uppercase English letters; unfortunately, he passed out before you could extract the actual password. But you also managed to hack into his server and steal a hashed version of his password. Based on some questions Hubert asked on StackOverflow, you suspect he used the FNV-1a hash algorithm for this purpose, perhaps under the misguided apprehension that it would be more secure to use a hash algorithm that no one else uses. Your job now is to figure out what passwords could possibly result in the given hash. If you can narrow it down to just a few, trying each one should be no problem.

The $32$-bit FNV-1a hash algorithm takes as input a list of bytes and produces a $32$-bit hash value, as follows:

• Initialize $\mathit{hash}$ to the FNV offset basis (defined below).

• For each byte $b$ in the input, from first to last:

  • Set $\mathit{hash}$ to the bitwise exclusive or (XOR) of itself with $b$.

  • Multiply $\mathit{hash}$ by the FNV prime and reduce the result modulo $2^{32}$.

• Output the value of $\mathit{hash}$.

For the $32$-bit version of FNV-1a, the FNV offset basis and FNV prime are defined as follows:

• FNV offset basis = $2\, 166\, 136\, 261$

• FNV prime = $2^{24} + 2^8 + 147 = 16\, 777\, 619$

Input

The first and only line of input contains an integer $n$, where $0 \leq n < 2^{32}$.

Output

Output all strings of exactly $5$ uppercase letters which hash to $n$, one per line. If there are multiple such strings, output them in lexicographic (dictionary) order. If there are no such strings, print impossible.

2118017030

HORSE

123456789

impossible