Background

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).

Problem Description

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$.

Input Format

Line $1$: read in $n, R$.

Lines $2$ to $n+1$: each line contains one encoding $S$.

Output Format

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.

2 6
HELLOWORLD
LETUSGO

NKRRUCUXRJ
10167740864629920000
RKZAYMU
20957073637500

Hint

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