/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君はテキストエディタを開発しています。このエディタには、複数のテキストファイルに対して一括で文字を置換する機能があります。
ある日、高橋君は N 個のテキストファイルを開きました。各ファイルには英小文字のみからなる文字列が1行ずつ書かれています。
高橋君はこれらのファイルに対して、 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
- 1 行目には、ファイルの個数を表す N と、置換操作の回数を表す Q が、スペース区切りで与えられる。
- 2 行目から N + 1 行目では、各ファイルに書かれた文字列が与えられる。
- 1 + i 行目では、 i 番目のファイルに書かれた文字列 S_i が与えられる。
- S_i は英小文字のみからなる。
- N + 2 行目から N + Q + 1 行目では、各置換操作の内容が与えられる。
- N + 1 + j 行目では、 j 回目の操作で置き換える元の文字 a_j と、置き換え先の文字 b_j がスペース区切りで与えられる。
- a_j , b_j はそれぞれ英小文字 1 文字である。
出力
T_1 T_2 : T_N
- N 行にわたって、すべての置換操作が完了した後の各ファイルの文字列を出力する。
- i 行目には、 i 番目のファイルに書かれている文字列 T_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
Score : 300 pts
Problem Statement
Takahashi is developing a text editor. This editor has a feature that performs bulk character replacement across multiple text files.
One day, Takahashi opened N text files. Each file contains a single line consisting of a string of lowercase English letters.
Takahashi will perform Q replacement operations on these files in order. In each operation, a specific character contained in all current files is replaced with another character all at once.
After all replacement operations are completed, output the string written in each file.
Constraints
- 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 consists only of lowercase English letters
- a_j, b_j are lowercase English letters
Input
N Q S_1 S_2 : S_N a_1 b_1 a_2 b_2 : a_Q b_Q
- The first line contains N, the number of files, and Q, the number of replacement operations, separated by a space.
- From the 2nd line to the (N + 1)-th line, the strings written in each file are given.
- The (1 + i)-th line contains the string S_i written in the i-th file.
- S_i consists only of lowercase English letters.
- From the (N + 2)-th line to the (N + Q + 1)-th line, the details of each replacement operation are given.
- The (N + 1 + j)-th line contains the original character a_j to be replaced and the destination character b_j in the j-th operation, separated by a space.
- a_j and b_j are each a single lowercase English letter.
Output
T_1 T_2 : T_N
- Output N lines, each containing the string in the corresponding file after all replacement operations are completed.
- The i-th line should contain the string T_i written in the i-th file.
Sample Input 1
3 2 abc dog banana a b b c
Sample Output 1
ccc dog ccncnc
Sample Input 2
2 3 hello world l x o a x l
Sample Output 2
hella warld
Sample Input 3
5 5 abcdefghij programming contest algorithm datastructure a z e a z e t s s t
Sample Output 3
ebcdafghij progremming contatt elgorithm detettructura
Sample Input 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
Sample Output 4
thhquihkhrownhoxjumpsovhrthhlhayhoh hhhhhhhhijklmnopqrstuvwxya hhhhhhhhhh aaaaayyyyyxxxxx hhlloworlhhromhomphtitivhprohrhmminh suhstitutionhiphhrhxhmplh rhplhhhmhntophrhtion quhrihshnhhilhs multiplhstrinhs hinhloutputthst
Sample Input 5
1 1 a a b
Sample Output 5
b