Feedback Cipher

Version: Phuoc Hung OJ Extended

Problem Statement

Use lowercase letters a..z with values a $=0$, b $=1$, $\ldots$, z $=25$.

Initially the current key is $k_1=K$, where $0\le K\le25$. At position $i$, let $p_i$ be the numeric value of the plaintext character and $c_i$ the numeric value of the ciphertext character.

For encryption,

After processing position $i$, update

For decryption, recover

then update the key using the recovered $p_i$ in the same way.

If $M=1$, encrypt $S$. If $M=2$, decrypt $S$. Processing is always performed from left to right.

Input

• Line 1 contains integers $M$ and $K$, where $M\in\{1,2\}$ and $0\le K\le25$.
• Line 2 contains $S$, consisting only of lowercase letters a..z.

Output

Print the resulting string after applying the requested mode.

Subtasks

• Subtask 1 (40 points): $1\le|S|\le10^3$.
• Subtask 2 (60 points): $1\le|S|\le10^6$.

Examples

Example 1

Input

1 3
hello

Output

kpbnc

Explanation

Initially $K=3$. The value of h is $7$, so the first encrypted value is $(7+3)\bmod26=10$, which is k. The key then becomes $(3+7+1)\bmod26=11$. Continuing from left to right produces kpbnc.

Example 2

Input

2 3
kpbnc

Output

hello

Explanation

Initially $K=3$. The value of encrypted k is $10$, so the first plaintext value is $(10-3+26)\bmod26=7$, which is h. Updating the key with each recovered plaintext value and continuing left to right reconstructs hello.