题目描述

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

对字符串 $S$ 进行 $Q$ 次修改。由两个整数和一个字符组成的元组 $(t_i,x_i,c_i)$ 表示第 $i$ 次修改 $(1 \le i \le Q)$，如下所示。

• 如果是 $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$ 的长度。

第二行输入字符串 $S$。

第三行输入一个整数 $Q$，表示修改的次数。

接下来的 $Q$ 行，每行输入三个内容 $t_i,x_i,c_i$，$t_i$ 为修改类型，$x_i,c_i$ 为对应的修改参数。

输出格式

输出一行，输出修改后的字符串。

样例

10
HELLOWORLD
3
2 1 a
1 1 H
1 6 W   

HelloWorld

14
IloveCPlusPlus
10
2 0 a
1 10 G
1 1 m
1 2 E
1 1 F
2 2 a
1 7 b
3 5 a
3 0 a
1 5 i

FEOViCBLUGPLUS

数据范围

• $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 = 'a'$
• $N,Q,t_i,x_i$ 都是正整数