题目描述

给定一个长度为 $N$ 的字符串 $S$，该字符串由大写和小写英文字母组成。

接下来将对字符串 $S$ 执行 $Q$ 次操作。第 $i$ 次操作（$1 \le i \le Q$）由一个三元组 $(t_i, x_i, c_i)$ 表示，具体规则如下：

• 如果 $t_i = 1$，则将 $S$ 的第 $x_i$ 个字符修改为 $c_i$。
• 如果 $t_i = 2$，则将 $S$ 中的所有大写字母转换为小写字母（此操作中不使用 $x_i$ 和 $c_i$）。
• 如果 $t_i = 3$，则将 $S$ 中的所有小写字母转换为大写字母（此操作中不使用 $x_i$ 和 $c_i$）。

请输出执行完 $Q$ 次操作后的最终字符串 $S$。

输入格式

第一行包含一个正整数 $N$ —— 字符串的长度。

第二行包含一个字符串 $S$。

第三行包含一个正整数 $Q$ —— 操作的次数。

接下来 $Q$ 行，每行包含两个整数 $t_i, x_i$ 和一个字符 $c_i$ —— 依次表示每次操作的参数。中间用空格隔开。

输出格式

输出一行，表示执行完所有操作后的最终字符串 $S$。

样例输入 1

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

样例输出 1

atcYber

样例输入 2

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

样例输出 2

TEEQUICKBROWMFiXJUGPFOVERTBELAZYDOG

说明

样例解释

在第一个样例中，初始字符串 $S$ 为 AtCoder。

• 第 $1$ 次操作将第 $4$ 个字符修改为 i，$S$ 变为 AtCider。
• 第 $2$ 次操作将所有小写字母转换为大写字母，$S$ 变为 ATCIDER。
• 第 $3$ 次操作将第 $5$ 个字符修改为 b，$S$ 变为 ATCIbER。
• 第 $4$ 次操作将所有大写字母转换为小写字母，$S$ 变为 atciber。
• 第 $5$ 次操作将第 $4$ 个字符修改为 Y，$S$ 变为 atcYber。

操作结束后，最终的字符串为 atcYber，因此输出 atcYber。

数据范围

• 对于所有测试点，保证 $1 \le N \le 5 \times 10^5$。
• 保证 $S$ 是一个长度为 $N$ 且仅由大写和小写英文字母组成的字符串。
• 对于所有测试点，保证 $1 \le Q \le 5 \times 10^5$。
• 保证 $1 \le t_i \le 3$（$1 \le i \le Q$）。
• 如果 $t_i = 1$，保证 $1 \le x_i \le N$（$1 \le i \le Q$）；$c_i$ 为大写或小写英文字母。
• 如果 $t_i \neq 1$，保证 $x_i = 0$ 且 $c_i = \text{'a'}$。
• 保证所有的 $N, Q, t_i, x_i$ 均为整数。