You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

随着信息化和数字化社会的发展，人们对信息安全和保密的重要性认识不断提高，于是在 $1997$ 年，美国国家标准局公布实施了“美国数据加密标准（DES）”

民间力量开始全面介入密码学的研究和应用中，采用的加密算法有DES、RSA、SHA等。随着对加密强度需求的不断提高，近期又出现了AES、ECC等。

Description

$playfair$ 加密算法经莱昂·普莱费尔提倡在英国军地和政府使用。 它有一些不太明显的特征：密文的字母数一定是偶数；任意两个同组的字母都不会相同，如果出现这种字符必是乱码和虚码。

它使用方便而且可以让频度分析法变成瞎子，在 $1854$ 到 $1855$ 年的克里米亚战争和 $1899$ 年的布尔战争中有广泛应用。但在 $1915$ 年的一战中被破译了。

编写分三步：

• 1.编制密码表
• 2.整理明文
• 3.编写密文

构成部分：

• 1.密钥
• 2.明文
• 3.密文
• 4.注明的某个字母代替的另一个字母

它依据一个 $5\times 5$ 的正方形组成的密码表来编写，密码表里排列有25个字母。如果一种语言字母超过 $25$ 个，可以去掉使用频率最少的一个。如，法语一般去掉w或k，德语则是把i和j合起来当成一个字母看待。英语中z使用最少，可以去掉它。

于是我们今天就来写一个 $playfair$ 加密算法，不过可能 稍微有点不同 ，请仔细阅读下面的加密规则：

1. 将 密钥（关键字） 除去重复出现的字母，将剩下的字母逐个逐个加入 $5 \times 5$ 的矩阵内，剩下的空间由未加入的英文字母依 $a-z \ (A-Z)$ 的顺序加入。注意，将 $q \ (Q)$ 去除，且将 $i$ 和 $j$ 视作同一字 （注意这里为了简化我们的操作，这里的密钥字符串保证 不存在 字母 q (Q)，但是密钥矩阵是存在字母 q 的 ,又由于大家都不喜欢 “弯的字母” 于是我们将所有的字母 j替换为 字母i）

2. 将要加密的明文分成两个一组。若组内的字母相同，将 $(q)\ Q$加到该组的 第一个字母 后，重新分组。若剩下一个字，也加入 $q\ (Q)$ 。（例如：eec分组为： eq ec）

3. 在加密的过程中，我们从前往后挑选出一组字母，并找出这一组中两个字母的位置：

   1. 若两个字母不同行也不同列，在矩阵中找出另外两个字母（ 组中 第一个字母对应 行 优先），使这四个字母成为一个长方形的四个角
   2. 若两个字母同行
      1. 若组中两个字母有一个是最右方，那么先取 行中最左边 的字母，然后取 组内最右边位置减一位置 的字母
      2. 若组中两个字母都没有在最右方，那么先取 组内最右边 的字母，然后取 组内最右边位置加一位置 的字母
   3. 若两个字母同列，取这两个字母下方的字母（若字母在最下方则取最上方的字母）。
      1. 若组中两个字母有一个是最下方，那么先取 列中最上边 的字母，然后取 组内最下边位置减一位置 的字母
      2. 若组中两个字母都没有在最下方，那么先取 组内最下边位置加一位置 的字母，然后取 组内最下边的位置 的字母

最后请将加密后的密文转化为大写字母输出

ps：更多详情请参考样例

Format

Input

第一行输入明文 $ming$ ( $1 <= |ming|<=2\times 10^6$ )

第二行输入密钥 $secret$ ( $1 <= |secret|<=2\times 10^6$ )

明文和密钥只包含大小写字母且密钥中不存在字母 Q or q

Output

请将加密后的密文全部转化为 大写 输出

Samples

wearefamily
SouthwestPetroleumUniversity

EPDWLBGAYPIZ

Hidethegoldinthetreestump
Playfairexample

BMODZBXDNABEKUDMUIXOMOUVIF

playfaircipher
PLAYFAIRISADIGRAMCIPHER

LAYFPYRSMRAMCD

explain

对于样例一我们的密钥字符串为：SouthwestPetroleumUniversity

于是我们能构造出密钥矩阵为：

我们将待加密串wearefamily 分组为：

WE AR EF AM IL YQ

加密后我们能得到：

EP DW LB GA YP IZ

然后连起来就得到了加密串：

EPDWLBGAYPIZ

Limitation

1s, 1024KiB for each test case.