Problem Description

题目描述

S 公司的固件工程师小伟在分析竞品时，发现对方的字符串保护层在编译期会生成一张单表替换字典：字典为 $26$ 个大写字母建立一个两两不同的对应关系，加密时把原字符串中的每个字母替换成它对应的那个字母，密文字母可以与原字母相同。

小伟目前手上有一对已经确认对应的密文和明文（来自被泄露的源码快照），他想据此还原整张字典。还原过程是：逐位扫描这对字符串，对明文中的字母 $x$，找到它在密文中对应位置的字母 $y$，认为 $y$ 就是 $x$ 的密字。扫描会在下列某个状态停止：

1. 扫描完毕，$26$ 个字母都作为明文字母出现过并取得了密字；
2. 扫描完毕，但存在某个（或某些）字母从未作为明文字母出现；
3. 扫描过程中发现手上的对应关系自相矛盾——即同一个明文字母对应了两个不同密字，或两个不同明文字母对应了同一个密字。

例：某段明文 XYZ 对应密文 ABA，说明 $X$ 与 $Z$ 的密字都是 A，违反"两两不同"，属于第 $3$ 种情况。

现在小伟又截获了一条密文，请你判断字典能否还原，并在可以还原时用它解出这条密文对应的明文。

输入格式

从文件 spy.in 读入，共三行，每行为一个长度在 $1$ 到 $100$ 之间的字符串。

第一行，小伟已确认的那条密文；

第二行，第一行密文所对应的明文；

第三行，需要解密的密文。

保证所有字符串仅由大写字母 A～Z 构成，且第一行长度与第二行相等。

输出格式

输出到文件 spy.out。

共一行。

若还原停止时出现第 $2,3$ 两种情况，输出 Failed；

否则输出利用还原出的字典解出第三条密文后得到的明文。

输入输出与文件要求

本题为文件输入输出（IO 赛制），必须使用 freopen 重定向。

freopen("spy.in", "r", stdin);    // 文件输入
freopen("spy.out", "w", stdout);  // 文件输出

样例

样例 1

输入

AA
AB
EOWIE

输出

Failed

样例 2

输入

QWERTYUIOPLKJHGFDSAZXCVBN
ABCDEFGHIJKLMNOPQRSTUVWXY
DSLIEWO

输出

Failed

样例 3

输入

MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP
YIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLL
FLSO

输出

NOIP

提示

样例 1 说明

明文 A 在第 $1$ 位对应密文 A，明文 B 在第 $2$ 位也对应密文 A。两个不同明文字母对应同一个密字，属于第 $3$ 种情况，输出 Failed。

样例 2 说明

还原出的字典只涉及 $25$ 个字母，Z 从未作为明文出现，属于第 $2$ 种情况，输出 Failed。

关键提示

要同时维护两个方向的映射：明文到密文、密文到明文。任一方向出现冲突（同一字母对应了两个不同字母）就输出 Failed；扫描结束后若明文字母不足 $26$ 种，同样输出 Failed。

评测方式

本题使用文件输入输出：评测时会把测试数据放到程序运行目录下的 spy.in， 并读取程序生成的 spy.out。请确认你的程序在没有任何标准输入的情况下也能正确运行。

数据规模与约定

对于 $100\%$ 的数据，三条字符串长度均不超过 $100$，且第一条与第二条长度相等，所有字符均为大写字母 A～Z。

Output Format

Failed