题目背景

1941年12月7日凌晨，珍珠港驻守美军通信员截获了一份日军电报。早上8时日军的正式进攻就会展开，为了减少太平洋战场伤亡，你被指派去协助破解密文。情报部门已得知了密文加密的层数和每层加密的方法。由于时间紧急，你只剩1秒的时间来破解日军的密文。

题目描述

据情报得知日军共有3种加密方式：

一、栅栏密码：

所谓栅栏密码，就是把要加密的明文分成L个一组，然后把每组的第1个字连起来，形成一段无规律的话。一般比较常见的是2栏的棚栏密码。

比如明文：THERE IS A CIPHER

去掉空格后变为：THEREISACIPHER

两个一组，得到：TH ER EI SA CI PH ER

先取出第一个字母：TEESCPE

再取出第二个字母：HRIAIHR

连在一起就是：TEESCPEHRIAIHR

这样就得到我们需要的密码了。

但也可能有更多的栏数。

注：若明文长度不能整除栏数，则分组后剩下的单独为一组，如：

THERE IS A CIPHER 3栏加密分组为：THE REI SAC IPH ER

先后取出第一二三个字母(最后一组只能取前两个)，加密后为:

TRSIE HEAPR EICH（去掉空格）。

二、维吉尼亚(Vigenère)密码：

维吉尼亚密码首先应用了“密钥”的思想，其在密码届具有十分重要的意义。

在密码学中，我们称需要加密的信息为明文，用 M 表示；称加密后的信息为密文，用 C 表示；而密钥是一种参数，是将明文转换为密文或将密文转换为明文的算法中输入的数据，记为 k。 在 Vigenère 密码中，密钥 k 是一个字母串，k=k1k2…kn。当明文 M=m1m2…mn 时，得到的密文 C=c1c2…cn，其中 ci=mi®ki，运算®的规则如下表所示：

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

A -A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

B -B C D E F G H I J K L M N O P Q R S T U V W X Y Z A

C -C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

D -D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

E -E F G H I J K L M N O P Q R S T U V W X Y Z A B C D

F -F G H I J K L M N O P Q R S T U V W X Y Z A B C D E

G -G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

H -H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

I -I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

J -J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

K -K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

L -L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

M -M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

N -N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

O -O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

P -P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

Q -Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

R -R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

S -S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

T -T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

U -U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

V -V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

W -W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

X -X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

Y -Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

Z -Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Vigenère 加密在操作时需要注意：

当明文 M 的长度大于密钥 k 的长度时，将密钥 k 重复使用。

例如，明文 M=Helloworld，密钥 k=abc 时，密文 C=Hfnlpyosnd。

三、QWE键盘码：

随着键盘普及，也出现了相应的键盘码。

这是一个常见的键盘,在左边字母区有三行字母分别为：

QWERTYUIOP

ASDFGHJKL

ZXCVBNM

从第一排第一列开始分别用Q替代A，W替代B……M替代Z以此类推。

如 CODING 加密后即为 EGROFU.

这对于现在来说算是简单的加密方法，但对于键盘不普及的二战时期却是一大难题。

输入格式

输入第一行为一个正整数N 表示截获的密文共用了N重密码加密。

第二行为一个字符串S表示加密后的密文。

以下3-N+2行共N行每行开头一个正整数K(1<=K<=3)表示对应的加密方式。

给出的加密方式按顺序给出，即给出的第I重加密为实际加密过程的第I重(1<=I<=N)。

若K=1则表示用栅栏密码加密，之后一个正整数L表示加密所用栏数。

若K=2则表示用维吉尼亚码加密，之后一个字符串T表示密钥。

若K=3则表示用QWE键盘码加密。

输出格式

共一行。一个字符串，表示破解N重加密后的明文。

2
YSLTRIQXSHTQTR
1 2
3

FULLSPEEDAHEAD

提示

n<=1000