分数: 300 分
问题陈述
Takahashi 正在开发一个文本编辑器。该编辑器具有跨多个文本文件执行批量字符替换的功能。
有一天,高桥开业了 N 文本文件。每个文件包含一行,由一串小写英文字母组成。
高桥将表演 Q 按顺序对这些文件进行替换操作。在每次操作中,所有当前文件中包含的特定字符都会立即替换为另一个字符。
所有替换操作完成后,输出每个文件中写入的字符串。
约束
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq |S_i| \leq 10^5
- \sum_{i=1}^{N} |S_i| \leq 10^6
- S_i 仅由小写英文字母组成
- a_j, b_j 为小写英文字母
输入
N Q S_1 S_2 : S_N a_1 b_1 a_2 b_2 : a_Q b_Q
- 第一行包含 N,文件数量,以及 Q,替换操作的数量,以空格分隔。
- 从第 2 行到 (N + 1)第行,给出了每个文件中写入的字符串。
- 的 (1 + i)- 第行包含字符串 S_i 写在 i-第一个文件。
- S_i 仅由小写英文字母组成。
- 从 (N + 2)第 行 (N + Q + 1)第行,给出了每个替换操作的详细信息。
- 的 (N + 1 + j)- 第行包含原始字符 a_j 要替换的字符和目标字符 b_j 在 j第一个操作,以空格分隔。
- a_j 和 b_j 都是一个小写英文字母。
输出
T_1 T_2 : T_N
- 输出 N 行,每行包含所有替换操作完成后对应文件中的字符串。
- 的 i- 第行应包含字符串 T_i 写在 i-第一个文件。
样本输入 1
3 2 abc dog banana a b b c
示例输出 1
ccc dog ccncnc
示例输入 2
2 3 hello world l x o a x l
示例输出 2
hella warld
示例输入 3
5 5 abcdefghij programming contest algorithm datastructure a z e a z e t s s t
示例输出 3
ebcdafghij progremming contatt elgorithm detettructura
示例输入 4
10 8 thequickbrownfoxjumpsoverthelazydog abcdefghijklmnopqrstuvwxyz aabbccddee zzzzzyyyyyxxxxx helloworldfromcompetitiveprogramming substitutioncipherexample replacementoperation queriesandfiles multiplestrings finaloutputtest a b b c c d d e e f f g g h z a
示例输出 4
thhquihkhrownhoxjumpsovhrthhlhayhoh hhhhhhhhijklmnopqrstuvwxya hhhhhhhhhh aaaaayyyyyxxxxx hhlloworlhhromhomphtitivhprohrhmminh suhstitutionhiphhrhxhmplh rhplhhhmhntophrhtion quhrihshnhhilhs multiplhstrinhs hinhloutputthst
示例输入 5
1 1 a a b
示例输出 5
b