Aftermath, a student in NTHU, is very good at programming. Today, as usual, she comes up with a programming problem but felt bored to solve it by herself(it’s too easy for her!). Thus, she left the problem to you, that is:

Given a string that consists of only lowercase Latin characters, there are Q operations to apply on this string.
There are two types of operations, with the following two forms:

• 1 A B
• 2 id C

For operation of type 1, you have to turn every A in the given string to B.
For operation of type 2, you have to set the idth character to C.

After the Q operations, you should print the resulting string in one line(remember to print a new line character).

• Hint 1: Whenever there’s a operation of type 2, the operations before it won’t affect the final result of the idth character.
• Hint 2: Should it be easier if we deal with the operations in reverse order?
• Hint 3: I want to be as smart as Aftermath.

The first line contains a string s, which consists of only lowercase Latin characters.

The second line contains a integer Q.

The next Q lines, each contains a operation.

Constraints

• 1≤|s|≤10⁶
• 1≤Q≤10⁵
• 0≤id≤|s|-1
• A,B,C ∈[a−z]

for testcases 1~3, 1≤|s|≤1000

for testcases 4~6, there’s no additional constraints.

Print the resulting string in one line after applying the Q operations.

(remember to print a new line character)