P5000 Hillwer Encoding

In the high-tech research center of Country Z, researchers use the most “advanced” Hillwer encoding (after all, this is the national secret vault, storing the most important confidential information~~QwQ).

Country Z is very technologically advanced and has always been a target coveted by other countries, and Country Y is one of them. After Country Y’s hackers worked day and night, they finally obtained the conversion method of Country Z’s **Hillwer** encoding and intercepted $n$ plaintext strings. BUT (there are always so many “buts”~), after studying **Hillwer** with all their effort, the hackers of Country Y were exhausted… so they cannot finish the task of converting **Hillwer** encoding. The leader of Country Y heard that in a faraway eastern land, there is a group of talented teenagers—yes, you who are sitting in front of the computer! The leader hopes you can help Country Y convert the encoding, and he will reward you with the **NOIP_AK Glory Laurel Crown**! The conversion rules of **Hillwer** encoding are as follows: For each plaintext string $S$, it is guaranteed to consist only of $26$ uppercase letters. Shift each letter backward by $R$ positions to get the intermediate string $S1$ (when $S$=`XYZ`, $R=2$, then $S1$=`ZAB`. That is, change it to the $R$-th letter after the current one; if it goes past `Z`, start again from `A`). Next, perform the “symbol-to-number” operation on the intermediate string: multiply the ASCII codes of each character in $S1$ to obtain the number string $Q$. The converted encoding is $Q$. To check whether you are slacking off, the leader also requires you to output the intermediate string $S1$.

Line $1$: read in $n, R$. Lines $2$ to $n+1$: each line contains one encoding $S$.

There are $2 \times n$ lines in total: - Odd-numbered lines: one intermediate string $S1$ per line. - Even-numbered lines: one converted encoding $Q$ per line.

For $30\%$ of the testdata, $1 \leq n \leq 10$, $1 \leq R \leq 10$. For $50\%$ of the testdata, $1 \leq n \leq 500$, $1 \leq R \leq 10^3$. For $100\%$ of the testdata, $1 \leq n \leq 500$, $1 \leq R \leq 10^5$, and the plaintext length is less than $600$. Translated by ChatGPT 5