Description

Z 国的科技十分发达，一直是各国觊觎的目标，Y 国就是其中之一。经过 Y 国黑客夜以继日的奋斗，终于获得了 Z 国 Hillwer 编码的转换方式，并且截获了 $n$ 条原码。BUT（总是有那么多但是~），Y 国的黑客们呕心沥血研究 Hillwer，都累得趴下了……所以，转换 Hillwer 编码的任务他们就无法完成。

Y 国元首听说在遥远的东方国度，有一群才华横溢的少年——就是坐在电脑前的你们！元首希望你能够帮助 Y 国转换编码，他将赠予你 NOIP_AK 荣耀桂冠！

Hillwer 编码的转换规则如下： 对于每一条原码 $S$，保证仅由 $26$ 个大写字母组成。将每个字母后移 $R$ 位，得到中转码 $S1$（当 $S$=XYZ,$R=2$ 时，$S1$=ZAB。即变成当前字母后 $R$ 个字母，超过 Z 则从 A 开始）。接着，将中转码进行“符转数”操作，将 $S1$ 每一位的 ASCII 码相乘，得到数串 $Q$。转换后的编码即为 $Q$。

元首为了检查你是不是偷懒，还要求你把中转码 $S1$ 也输出。

Input Format

第 $1$ 行，读入 $n , R$。

第 $2 \sim n+1$ 行，每行一条编码 $S$。

Output Format

共 $2 \times n$ 行:

• 奇数行，每行一条中转码 $S1$；

• 偶数行，每行一条转换后的编码 $Q$。

2 6
HELLOWORLD
LETUSGO

NKRRUCUXRJ
10167740864629920000
RKZAYMU
20957073637500

Hint

对于 $30\%$ 的数据，$1 \leq n \leq 10 ,1 \leq R \leq 10$；

对于 $50\%$ 的数据，$1 \leq n \leq 500 ,1 \leq R \leq 10^3$；

对于 $100\%$ 的数据，$1 \leq n \leq 500 ,1 \leq R \leq 10^5$，原码长度小于 $600$。