问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and will generate a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program.
### Question:
You are given a string S of length N consisting of lowercase English letters.
You will perform an operation Q times on the string S.
The i-th operation (1\leq i\leq Q) is represented by a pair of characters (c _ i,d _ i), which corresponds to the following operation:

- Replace all occurrences of the character c _ i in S with the character d _ i.

Print the string S after all operations are completed.

Input

The input is given from Standard Input in the following format:
N
S
Q
c _ 1 d _ 1
c _ 2 d _ 2
\vdots
c _ Q d _ Q

Output

Print the string S after all operations are completed.

Constraints


- 1\leq N\leq2\times10^5
- S is a string of length N consisting of lowercase English letters.
- 1\leq Q\leq2\times10^5
- c _ i and d _ i are lowercase English letters (1\leq i\leq Q).
- N and Q are integers.

Sample Input 1

7
atcoder
4
r a
t e
d v
a r

Sample Output 1

recover

S changes as follows: atcoder → atcodea → aecodea → aecovea → recover.
For example, in the fourth operation, all occurrences of a in S={}aecovea (the first and seventh characters) are replaced with r, resulting in S={}recover.
After all operations are completed, S={}recover, so print recover.

Sample Input 2

3
abc
4
a a
s k
n n
z b

Sample Output 2

abc

There may be operations where c _ i=d _ i or S does not contain c _ i.

Sample Input 3

34
supercalifragilisticexpialidocious
20
g c
l g
g m
c m
r o
s e
a a
o f
f s
e t
t l
d v
p k
v h
x i
h n
n j
i r
s i
u a

Sample Output 3

laklimamriiamrmrllrmlrkramrjimrial

### Format: Read the inputs from stdin solve the problem and write the answer to stdout (do not directly test on the sample inputs). Enclose your code within delimiters as follows.
```python
# YOUR CODE HERE
```

### Answer: (use the provided format with backticks)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
S = list(data[1])
Q = int(data[2])

for i in range(Q):
c, d = data[3 + 2 * i], data[4 + 2 * i]
S = [d if char == c else char for char in S]

print(''.join(S))
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
deepseek-r1

```python
def main():
import sys
input = sys.stdin.read().split()
ptr = 0
N = int(input[ptr])
ptr += 1
S = input[ptr]
ptr += 1
Q = int(input[ptr])
ptr += 1

# Initialize substitution map: each character maps to itself initially
m = list(range(26))
for _ in range(Q):
c = input[ptr]
d = input[ptr + 1]
ptr += 2
cc = ord(c) - ord('a')
dc = ord(d) - ord('a')
# Update all characters that currently map to cc to map to dc
for i in range(26):
if m[i] == cc:
m[i] = dc

# Build the result string
res = []
for char in S:
idx = ord(char) - ord('a')
res.append(chr(m[idx] + ord('a')))
print(''.join(res))

if __name__ == '__main__':
main()
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading
def main():
import sys
import bisect

sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

N = int(sys.stdin.readline())
S = sys.stdin.readline().strip()
Q = int(sys.stdin.readline())
operations = []
for _ in range(Q):
c_i, d_i = sys.stdin.readline().strip().split()
operations.append((c_i, d_i))
mapping = {chr(ord('a') + i): chr(ord('a') + i) for i in range(26)}

for c_i, d_i in reversed(operations):
mapping[c_i] = mapping[d_i]

result = ''.join(mapping[c] for c in S)
print(result)


threading.Thread(target=main).start()
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
gpt-4o-2024-08-06 ```python
# YOUR CODE HERE
import sys
input = sys.stdin.read

def main():
data = input().split()
N = int(data[0])
S = data[1]
Q = int(data[2])

operations = data[3:]

# Create a mapping of characters to their final replacements
replacement_map = {}

for i in range(Q):
c_i = operations[2 * i]
d_i = operations[2 * i + 1]

# If c_i is already mapped to something, we need to update the mapping
# to reflect the new replacement
if c_i in replacement_map:
# Update the mapping for all characters that map to c_i
for key in list(replacement_map.keys()):
if replacement_map[key] == c_i:
replacement_map[key] = d_i
# Also update c_i itself
replacement_map[c_i] = d_i
else:
# Directly map c_i to d_i
replacement_map[c_i] = d_i

# Now apply the final replacement map to the string S
result = []
for char in S:
if char in replacement_map:
result.append(replacement_map[char])
else:
result.append(char)

print(''.join(result))

main()
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
DeepSeek-Coder-V2-Lite-Instruct ```python
# YOUR CODE HERE
import sys

# Read input
N = int(input())
S = input()
Q = int(input())

# Initialize the string as a list to allow modifications
S_list = list(S)

# Perform the operations
for _ in range(Q):
c_i, d_i = input().split()
for i in range(N):
if S_list[i] == c_i:
S_list[i] = d_i

# Convert the list back to a string and print it
print(''.join(S_list))
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
Meta-Llama-3.1-405B-Instruct-Turbo ```python
import sys

def solve():
n = int(input())
s = input()
q = int(input())
mp = {}
for i in range(q):
c, d = input().split()
mp[c] = d

for i in range(26):
c = chr(ord('a') + i)
d = c
while d in mp:
d = mp[d]
mp[c] = d

ans = []
for c in s:
ans.append(mp[c])

print(''.join(ans))

if __name__ == '__main__':
solve()
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
Meta-Llama-3.1-70B-Instruct-Turbo ```python
import sys

def solve():
n = int(input())
s = input()
q = int(input())
queries = [input().split() for _ in range(q)]

mapping = {}
for c, d in queries:
if c in mapping:
mapping[d] = mapping[c]
else:
mapping[d] = d
mapping[c] = d

result = []
for char in s:
while char in mapping:
char = mapping[char]
result.append(char)

print(''.join(result))

if __name__ == '__main__':
solve()
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
Qwen2-72B-Instruct ```python
n = int(input())
s = list(input())
q = int(input())

operations = [input().split() for _ in range(q)]

replacements = {}

for c, d in reversed(operations):
if c in replacements:
replacements[c] = d
else:
replacements[c] = d

for i in range(n):
if s[i] in replacements:
s[i] = replacements[s[i]]

print("".join(s))
```
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
baichuan4 ```python
# YOUR CODE HERE
import sys

# Read input values
N = int(sys.stdin.readline().strip())
S = sys.stdin.readline().strip()
Q = int(sys.stdin.readline().strip())

# Perform the operations
for _ in range(Q):
c_i, d_i = sys.stdin.readline().strip().split()
S = S.replace(c_i, d_i)

# Print the final string
print(S)
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
doubao ```python
N = int(input())
S = input()
Q = int(input())

for _ in range(Q):
c, d = input().split()
S = S.replace(c, d)

print(S)
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading
def main():
import sys
import bisect

sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

N = int(sys.stdin.readline())
S = sys.stdin.readline().strip()
Q = int(sys.stdin.readline())
operations = []
for _ in range(Q):
c_i, d_i = sys.stdin.readline().strip().split()
operations.append((c_i, d_i))
mapping = {chr(ord('a') + i): chr(ord('a') + i) for i in range(26)}

for c_i, d_i in reversed(operations):
mapping[c_i] = mapping[d_i]

result = ''.join(mapping[c] for c in S)
print(result)


threading.Thread(target=main).start()
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
kimi ```python
# YOUR CODE HERE
n = int(input())
s = list(input())
q = int(input())
d = {}
for _ in range(q):
(c, d_) = input().split()
if c in d:
d[c] = d_ if d[c] != c else d_
else:
d[c] = d_
for i in range(n):
if s[i] in d:
s[i] = d[s[i]]
print(''.join(s))
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
minimax ```python
# YOUR CODE HERE
from collections import defaultdict

# Read the inputs
N = int(input())
S = input()
Q = int(input())
operations = defaultdict(str)

# Process the operations
for _ in range(Q):
c_i, d_i = input().split()
operations[c_i] = d_i

# Apply the operations to the string S
for c_i, d_i in operations.items():
S = S.replace(c_i, d_i)

# Print the final string S
print(S)
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
wenxinyiyan ```python
# Read the input values
N = int(input())
S = input()
Q = int(input())

# Perform the operations
for _ in range(Q):
c_i, d_i = input().split()
S = S.replace(c_i, d_i)

# Print the final string
print(S)
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
zhipu ```python
def main():
import sys
input = sys.stdin.read
data = input().split()

n = int(data[0])
s = list(data[1])
q = int(data[2])

operations = data[3:]

# Create a dictionary to map characters to their final replacements
char_map = {}

for i in range(q):
c_i = operations[2 * i]
d_i = operations[2 * i + 1]

# If c_i is already mapped, update the mapping to the new character d_i
if c_i in char_map:
# If d_i is also mapped, we need to map c_i to the final character of d_i
if d_i in char_map:
char_map[c_i] = char_map[d_i]
else:
char_map[c_i] = d_i
else:
char_map[c_i] = d_i

# Apply the final mappings to the string s
for i in range(n):
if s[i] in char_map:
s[i] = char_map[s[i]]

# Join the list into a string and print the result
print(''.join(s))

if __name__ == "__main__":
main()
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]
deepseek-v3 ```python
# YOUR CODE HERE
def main():
import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
S = data[1]
Q = int(data[2])

# Initialize a mapping from each character to itself
mapping = {chr(ord('a') + i): chr(ord('a') + i) for i in range(26)}

# Process each operation
index = 3
for _ in range(Q):
c = data[index]
d = data[index + 1]
index += 2
# Update the mapping: for all characters that map to c, map them to d
for key in mapping:
if mapping[key] == c:
mapping[key] = d

# Apply the final mapping to the string S
result = []
for char in S:
result.append(mapping[char])

print(''.join(result))

if __name__ == "__main__":
main()
```		 [{"input": "7\natcoder\n4\nr a\nt e\nd v\na r\n", "output": "recover\n", "testtype": "stdin"}, {"input": "3\nabc\n4\na a\ns k\nn n\nz b\n", "output": "abc\n", "testtype": "stdin"}, {"input": "34\nsupercalifragilisticexpialidocious\n20\ng c\nl g\ng m\nc m\nr o\ns e\na a\no f\nf s\ne t\nt l\nd v\np k\nv h\nx i\nh n\nn j\ni r\ns i\nu a\n", "output": "laklimamriiamrmrllrmlrkramrjimrial\n", "testtype": "stdin"}]