题目背景

在Z国的高科技研究中心，科研人员使用的都是最“先进”的Hillwer编码（毕竟这里可是国家机密库，储存着最重要的机密资料~~QwQ）。

题目描述

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$每一位的ACS码（即ASCLL码）相乘，得到数串$Q$。转换后的编码即为$Q$。

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

输入格式

第1行，读入$n$，$R$。 第2~$n$+1行，每行一条编码S。

输出格式

共$n$*2行， 奇数行，每行一条中转码$S1$； 偶数行，每行一条转换后的编码$Q$。

2 6
HELLOWORLD
LETUSGO

NKRRUCUXRJ
10167740864629920000
RKZAYMU
20957073637500

提示

对于 $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