# Alien Codebreaking

You’ve intercepted encrypted communications between Martian diplomats. Since Martian diplomats are often spies, you decide to decrypt the messages. While the Martians have skilled rocket tech, they lag behind in number theory considerably, which compromises their encryption protocol.

Fortunately for you, spies friendly to you have reverse engineered the Martian protocol. It turns out that the Martians are using a shift-based cipher combined with a very long one-time pad. More specifically, the decryption procedure works as follows:

Step 1: Define the function $f(x) = (33x + 1) \mod
2^{20}$.

Further define $f^1(x) = f(x)$, $f^2(x) = f(f(x))$, $f^3(x) = f(f(f(x)))$, and so on.

Step 2: Create a $X$ by $X$ size grid, fill the upper left corner with $f^1(0)$, the next cell to the right with $f^2(0)$, $f^3(0)$ etc. Once the top row is filled, continue to the cell below the upper left cell, and fill with $f^{X+1}(0)$. Continue this process until all rows are filled.

Step 3: Sum all the values in every column, and take those values mod $2^{20}$.

Step 4: Concatenate the base-10 representations of the
column sums together, to get a very long base-10 number. For
instance, if you had column sums of `10` and `12` for the
first and second column, the leftmost four digits of the
resulting value would be `1012`.

Step 5: Convert the result of step 4 from base $10$ to base $27$. This will yield the one-time pad the Martians used.

Step 6: For each letter $l$ of the intercepted message, shift
the letter by the amount given by the corresponding digit of
step 5, base $27$.
“Shifting” means to add the digit at the corresponding position
of the pad to the value of the letter in the encrypted message
and then to compute its remainder modulo $27$. You may assume that both the
encrypted and the decrypted message consist of only uppercase
English characters ‘`A`’ through
‘`Z`’ and spaces, which are assigned
values $0 \ldots 26$
(`A = 0`, `B =
1`, ... `Z = 25`, `SPACE = 26`). Thus, if the encrypted message has
letter ‘`D`’ in position $3$, and the $3^{\text {rd}}$ base-$27$ digit of the pad is $25$, then the decrypted letter after
shifting would be $3 + 25 = 1
\mod 27$ which is ‘`B`’.

Step 7: Output the decrypted message.

## Input

The first line of the input contains two positive integers, $N$ ($1 \le N \le 10^6$), and $X$ ($1 \le X \le 2.5 \cdot 10^5$). It is guaranteed that the base $27$ result of step 5 will be longer or equal to the length of the intercepted message. The second line of the input contains a string consisting of uppercase letters and spaces of length $N$, the encrypted text.

## Output

Output the decrypted text.

Sample Input 1 | Sample Output 1 |
---|---|

14 4 JQ IRKEYFG EXQ |
THIS IS A TEST |

Sample Input 2 | Sample Output 2 |
---|---|

43 100000 BLNAMOTPRRNIXRNMPIWHXDZTRQJXRKIAIEEIIPJLGZP |
FRIENDS ROMANS COUNTRYMEN LEND ME YOUR EARS |