“你用了什么解法？” “暴力。” “我也是，暴力。” “连你也是吗，布鲁图斯（Brute）？” —— 选自参赛者的讨论
瞧，这是一种创新的加密方法，灵感源自古老智慧与现代简约的完美平衡！
你一定对凯撒密码（Caesar cipher）非常熟悉。它极其简单：将消息中的每个字母在字母表中向右移动相同的位数。如果移动超出了字母表的范围，则从头开始。例如，单词 fusion 偏移 6 位后变为单词 layout。要解密消息，只需将每个字母向左移动相同的位数即可。
这种新的加密方法被称为“凯撒沙拉密码”（Caesar Salad cipher）。它与古老的原型非常相似，但更加可靠！它适用于由 a 到 z 的字母组成的单词。拉丁字母表中的每个字母对应一个 0 到 25 的数字编码：字母 a 的编码为 0，字母 b 的编码为 1，c 的编码为 2，依此类推，直到字母 z 的编码为 25。凯撒沙拉密码的工作原理如下：
- 设 $(a_1, a_2, \dots, a_k)$ 为长度为 $k$ 的原始消息中字母的数字编码。例如，单词
delta对应的编码序列为 $(3, 4, 11, 19, 0)$。 - 选择一个偏移量 $x$，它是 1 到 25（含）之间的一个整数。请注意，与原始凯撒密码一样，出于安全原因，不能选择零偏移。
- 令 $b_1 := (a_1 + x) \bmod 26$。
- 接下来，对于 2 到 $k$ 之间的每个 $i$，令 $b_i := (a_i + b_{i-1} + x) \bmod 26$。
- 编码序列 $(b_1, b_2, \dots, b_k)$ 对应加密后的消息。因此，在以 $x = 20$ 的偏移量加密单词
delta后，我们得到 $(23, 21, 0, 13, 7)$，对应单词xvanh。
现在，闲话少说，是时候将你的新知识付诸实践了！你需要开发一个用于传输数字密钥的协议。一个数字密钥由 $n$ 个单词组成，每个单词包含 $k$ 个拉丁字母。在这些单词中，可能会有重复，但总的来说，它们的顺序并不重要。在通过公开信道传输之前，会混入 $n$ 个长度为 $k$ 的新单词，这些新单词是原始单词经过凯撒沙拉密码加密后得到的。这 $n$ 个单词中的每一个都可以使用不同的偏移量进行加密。得到的包含 $2n$ 个单词的多重集（以任意顺序打乱）被称为“带杂质的数字密钥”。
你的任务是实现该协议的两个部分。在第一部分中，根据给定的数字密钥，你需要生成一个带杂质的密钥；在第二部分中，从你的算法生成的带杂质的密钥中提取出原始数字密钥的所有单词。
输入格式
对于每个测试点，你的程序将被运行两次。在第一次运行中，输入将由原始数据组成；在第二次运行中，输入将是你的加密程序加密后得到的数据。
每个测试点包含多个测试用例。第一行包含一个由大写拉丁字母组成的单词 $S$ 和一个整数 $t$ ($1 \le t \le 1000$)：测试用例的数量。如果 $S = \text{ENCODE}$，这是第一次运行，对于每个测试用例，你需要生成一个带杂质的数字密钥。如果 $S = \text{DECODE}$，这是第二次运行，对于每个测试用例，你需要从带杂质的密钥中提取出原始数字密钥的单词。接下来是测试用例的描述。
每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 25$，$1 \le k \le 20$)：原始数字密钥中的单词数量以及每个单词的长度。
如果 $S = \text{ENCODE}$，接下来的 $n$ 行中，每行包含一个由 $k$ 个小写拉丁字母组成的单词。这 $n$ 个单词定义了原始数字密钥。部分单词可能相同。
如果 $S = \text{DECODE}$，接下来的 $2n$ 行中，每行包含一个由 $k$ 个小写拉丁字母组成的单词。这 $2n$ 个单词定义了带杂质的数字密钥，即你的程序在第一次运行中输出的内容。带杂质的密钥中单词的顺序可以是任意的。
输出格式
如果 $S = \text{ENCODE}$，对于每个测试用例，输出 $n$ 个长度为 $k$ 的单词：使用凯撒沙拉密码加密后的单词。每个单词可以选择不同的偏移量，但加密后单词的输出顺序必须与原始单词的顺序相对应。在第二次运行之前，这些加密后的单词将与 $n$ 个原始单词混合。
如果 $S = \text{DECODE}$，对于每个测试用例，输出 $n$ 个长度为 $k$ 的单词：恢复出的数字密钥，它必须与原始密钥相匹配。在第二次运行中，你可以以任意顺序输出数字密钥的单词。
字母大小写很关键：输出的拉丁字母必须是小写。
样例
输入格式 1
ENCODE 2 4 5 delta alpha alpha prime 1 20 petrozavodskprogcamp DECODE 2 4 5 alpha prime kfevf delta zjxdc alpha rkuio xvanh 1 20 vfebvaghbkiytqkwekcx petrozavodskprogcamp
输出格式 1
xvanh zjxdc kfevf rkuio vfebvaghbkiytqkwekcx alpha delta prime alpha petrozavodskprogcamp
说明
样例展示了两次运行的输入和输出数据格式。为了清晰起见，第一次和第二次运行的数据描述之间用空行隔开。
对于第一个测试用例，单词分别选择了 20、25、10 和 2 的偏移量。 对于第二个测试用例，在第一次运行后，该单词被以 6 的偏移量加密。