题目描述

第二次世界大战期间，德国军队主要使用一种特殊机器来保护通信安全：恩尼格玛密码机（如图4所示）。破译恩尼格玛密码是盟军密码分析的主要成功案例之一，这一胜利主要归功于数字计算的出现和英国布莱切利园（秘密密码分析总部）工作人员的天才。原因是虽然恩尼格玛密码确实能抵抗纸笔攻击，但使用数字计算机却相当容易破解。

图4：一台恩尼格玛机器（图片来源：http://www.nsa.gov/museum/enigma.html）。

恩尼格玛是一种转子机，这是当时流行的一种加密方法。转子是一个绝缘圆盘，其外围两侧均匀分布着电触点，每个触点对应一个字母。绝缘材料内部的导电路径将两侧的触点成对连接。从一侧进入的电流通过转子横截面的内部路径，从另一侧的某个触点流出（图5展示了两个转子的3D可视化效果）。图6展示了完整转子系统的示意侧视图，显示恩尼格玛有三个转子$π_0$、$π_2$以及一个额外的反射转子$π_R$。

恩尼格玛的输入是一个没有空格的字母字符流。每个字符都经过以下步骤处理：

1. 明文首先经过初始置换$IP$，由插线板实现。
2. 步骤1得到的字符通过三个转子$π_0$、$π_2$。
3. 结果字符再通过反射转子$π_R$。
4. 步骤3得到的字符反向通过转子$π_2$、$π_0$（即方向相反）。
5. 步骤4得到的字符经过初始置换$IP$的逆置换$IP^{-1}$。

转子使用的有趣之处在于，在处理每个字符后，每个转子可能会旋转一定角度（即一定数量的字母）再处理下一个字符。在恩尼格玛中，转子$π_0$每处理一个新字符就逆时针旋转1个位置。当$π_0$完成一整圈旋转（即处理26个字符后），转子$π_1$移动1个字符。类似地，当$π_1$完成一整圈旋转后，转子$π_2$旋转1个字符，反射转子$π_R$在$π_2$完成旋转后移动。显然，$π_R$是四个转子中转得最慢的。

只要反射转子$π_R$实现的置换是一个对合置换，上述过程既可用于加密也可用于解密。这意味着$π_R = π_R^{-1}$，或者等价地，当$ζ=π_R(ξ)$时，有$ξ=π_R(ζ)$。题目假设这一条件成立。

恩尼格玛的密钥包括：(1) 转子$π_0$、$π_2$和$π_R$，(2) 插线板置换$IP$，(3) 转子$π_0$、$π_2$和$π_R$的初始旋转位移$k_0$、$k_1$、$k_2$、$k_R$（见下文）。在国防军型号中，转子很少更换，且从四个可能的转子中选择。

问题

你和你的笔记本电脑一起穿越到了布莱切利园，需要帮助破译当天截获的一些消息。你会得到完整的密文、部分明文和部分恩尼格玛密钥。你的任务是确定正确的密钥，最终通过解码密文补全明文。

输入格式

第一行包含场景数量。

每个场景以恩尼格玛的密钥开头。密钥由6行指定：

• 前四行分别给出转子$π_0$、$π_2$和$π_R$的规范，以小写字母序列表示。第$i$个字符（$1 \leq i \leq 26$）给出字母表中第$i$个字符的映射（例如"bha..."表示"a"映射为"b"，"b"映射为"h"，"c"映射为"a"等）。物理上，字符序列是从转子堆栈$π_0$、...、$π_R$的前面看顺时针方向给出的。
• 接下来一行以类似方式给出插线板置换$IP$。
• 第六行给出四个转子$π_0$、$π_2$和$π_R$的初始位移$k_0$、$k_1$、$k_2$、$k_R$，由四个字符组成的字符串表示，其中"a"表示转子处于原始位置（由上述转子规范定义），"b"表示按通常方式旋转1个位置等。例如"dgaa"表示转子$π_0$初始位移为3，$π_1$为6，$π_2$和$π_R$都处于原始位置。

密钥之后是两行，每行包含至少1个、最多80个小写字母，没有其他字符。第一行是明文，第二行是密文。明文和密钥的任何部分都可能不完整，即字符串中的某些位置可能是问号"?"。输入中的问号数量最多为3个。

输出格式

每个场景的输出以一行"Scenario #i:"开头，其中$i$是从1开始的场景编号。下一行输出完整的解密明文。可以假设解存在且唯一。每个场景的输出以空行结束。

输入样例1

2
wfbtiznuvcqejpokshxgmadyrl
hmrgnqpkjcaivwluebfzsyxtdo
druahlbfzvgmwckxpiqysontje
owtvskypjifmluahrqecndbzgx
?bcdefghijklmnopqrstuvwxyz
aaaa
manyorganizationsrelyoncom??ters
grsuztldsznkwnerdpfbovvqnobkyiqn
oqzunvhtxwryfebicmjpklsgda
zupogrskynxtwdfqvbliejcmha
kzvlyjuodmscewxtfbphriqgna
gbcnylaztwkfmdspqvoiurjxeh
rfyhkxbuvplgtqmdiewjosznca
dmeo
???
ave

输出样例1

Scenario #1:
manyorganizationsrelyoncomputers

Scenario #2:
acm

来源

2001年西北欧地区