実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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