题目描述

一个长度为 $N$ 的字符串 $S$，现在要修改 $Q$ 次，每次修改如下：

• $1$ $x_i$ $c_i$，表示把 $x_i$ 位改成 $c_i$，注意，字符串的首位为第一位。
• $2$ $x_i$ $c_i$，表示把所有的大写字母都转变为小写字母，此时 $x_i$、$c_i$ 无实际作用。
• $3$ $x_i$ $c_i$，表示把所有的小写字母都转变为大写字母，此时 $x_i$、$c_i$ 无实际作用。

请你输出 $Q$ 次操作后的字符串 $S$。

输入格式

第一行一个整数 $N$，$1 \leq x_i \leq N \leq 5 \times 10^5$

第二行一个长度为 $N$ 的字符串。

第三行一个整数 $Q$，$1 \leq q \leq 5 \times 10^5$。

接下来 $Q$ 行，每行输入一个操作。

输出格式

输出 $Q$ 次操作后的字符串。

7
AtCoder
5
1 4 i
3 0 a
1 5 b
2 0 a
1 4 Y

atcYber

35
TheQuickBrownFoxJumpsOverTheLazyDog
10
2 0 a
1 19 G
1 13 m
1 2 E
1 21 F
2 0 a
1 27 b
3 0 a
3 0 a
1 15 i

TEEQUICKBROWMFiXJUGPFOVERTBELAZYDOG