密码学
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

考虑一种加密方式,它需要一个任意长度的原文 和秘钥 ,其中要求原文和秘钥只包含大写和小写的英文字符。
首先定义字符之间的加密,用字符 去加密字符 的结果是:
  1. 首先把 转成数字 。转换的规则是,小写字母 依次对应 ,大写字母依次对应
  2. 计算 的和 ,对 取模,即计算
  3. 返回数字 对应的字符。
现在来讲如何用秘钥 来加密原文
  1. 如果秘钥的 的长度小于 ,那么不停重复 直到长度不小于 为止。举例来说,如果原文是 ,秘钥是 ,那么秘钥需要被重复称
  2. 假设原文的长度是 ,那么对于每一个 的数字 ,都用 的第 个字符去加密 的第 个字符。
  3. 返回结果。
那么用 去加密 的结果就是:
现在火山哥有 个字符串,s_1s_n,他对这些字符串做了 次加密操作:第 次加密操作用第 去加密 ,并把 替换成加密结果。
现在依次给出 次加密操作,以及加密操作结束后每一个字符串的模样,你可以还原出这 个字符串原来的模样吗?

输入描述:

第一行输入两个整数  
接下来 行每行输入两个整数 x_i,y_i ,表示依次加密操作,保证 x_i 不等于 y_i
接下来 行每行输入一个字符串,表示加密最后的结果。字符串的长度在 之间,只包含大小写英文字符。

输出描述:

输出  行,每行一个字符串,表示原本的字符串。
示例1

输入

复制
2 1
1 2
PKUSAA
QOcbINV

输出

复制
PKUSAA
beijing