← 返回题目列表

AtCoder · oupc2023_day1_c

C. 凯撒密码

中文机器翻译题面 查看原题

配点 : 100 点

問題文

凯撒密码是 3 字符移位很常见,但这里 0 \leq k < 26 中的任意键 假设您移动了 k 的数量。
明文由小写英文字母组成,需要在小写英文字母范围内进行移位。

凯撒密码详解

加密前的文本称为明文,加密后的文本称为密文。将密文转换回明文的过程称为解密。

键 k (0 \leq k < 26)。加密时,每个字符都是 k 更改为下一个字符。然而,z 之后的下一个字符是 a 。

例如,如果密钥是 考虑 2 的情况。明文 加密 ayz 有 cab 。

N 明文候选。i 候选人是 S_i 并且所有这些字符数都是 您将获得 M 。

Q 密文,因此请解密它们。j 密文是 T_j 是使用凯撒密码加密的明文候选之一。每个密文都使用独立选择的密钥进行加密。

确定明文候选,以便在加密时始终可以识别它们。换句话说,S_a 和 S_b (a \ne b) 都是任意键。 不存在用 k_a, k_b 加密时的密文匹配的情况。

制約

  • 1 \leq N \leq 200{,}000
  • 1 \leq M \leq 200{,}000
  • 1 \leq Q \leq 200{,}000
  • M \max (N, Q) \leq 200{,}000
  • N, M, Q 是一个整数
  • S_i, T_j 是小写字母的长度 M 字符串
  • 加密后始终可以识别明文候选者
  • T_j 是使用凯撒密码加密的明文候选之一。 请输出

入力

输入是按以下格式从标准输入给出的。

N M
S_1
S_2
\vdots
S_N
Q
T_1
T_2
\vdots
T_Q

出力

Q 行。

j 行中,j 第密文 请输出 T_j 的解密版本。


入力例 1

2 3
ayz
bbb
2
cab
aaa

出力例 1

ayz
bbb

键 2 作为 ayz 有 cab 。
键 25 作为 bbb 有 aaa 。


入力例 2

3 7
rainbou
osakauv
atcoder
2
ptblbvw
envaobh

出力例 2

osakauv
rainbou