103143: [Atcoder]ABC314 D - LOWER

Problem Statement

You are given a string $S$ of length $N$ consisting of uppercase and lowercase English letters.

Let us perform $Q$ operations on the string $S$. The $i$-th operation $(1\leq i\leq Q)$ is represented by a tuple $(t _ i,x _ i,c _ i)$ of two integers and one character, as follows.

• If $t _ i=1$, change the $x _ i$-th character of $S$ to $c _ i$.
• If $t _ i=2$, convert all uppercase letters in $S$ to lowercase (do not use $x _ i,c _ i$ for this operation).
• If $t _ i=3$, convert all lowercase letters in $S$ to uppercase (do not use $x _ i,c _ i$ for this operation).

Print the $S$ after the $Q$ operations.

Constraints

• $1\leq N\leq5\times10^5$
• $S$ is a string of length $N$ consisting of uppercase and lowercase English letters.
• $1\leq Q\leq5\times10^5$
• $1\leq t _ i\leq3\ (1\leq i\leq Q)$
• If $t _ i=1$, then $1\leq x _ i\leq N\ (1\leq i\leq Q)$.
• $c _ i$ is an uppercase or lowercase English letter.
• If $t _ i\neq 1$, then $x _ i=0$ and $c _ i=$ 'a'.
• $N,Q,t _ i,x _ i$ are all integers.

Input

The input is given from Standard Input in the following format:

$N$
$S$
$Q$
$t _ 1$ $x _ 1$ $c _ 1$
$t _ 2$ $x _ 2$ $c _ 2$
$\vdots$
$t _ Q$ $x _ Q$ $c _ Q$

Output

Print the answer in a single line.

Sample Input 1

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

Sample Output 1

atcYber

Initially, the string $S$ is AtCoder.

• The first operation changes the $4$-th character to i, changing $S$ to AtCider.
• The second operation converts all lowercase letters to uppercase, changing $S$ to ATCIDER.
• The third operation changes the $5$-th character to b, changing $S$ to ATCIbER.
• The fourth operation converts all uppercase letters to lowercase, changing $S$ to atciber.
• The fifth operation changes the $4$-th character to Y, changing $S$ to atcYber.

After the operations, the string $S$ is atcYber, so print atcYber.

Sample Input 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

Sample Output 2

TEEQUICKBROWMFiXJUGPFOVERTBELAZYDOG

问题描述

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

我们要对字符串 $S$ 执行 $Q$ 次操作。第 $i$ 次操作 $(1\leq i\leq 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$。

约束

• $1\leq N\leq5\times10^5$
• $S$ 是一个长度为 $N$ 的字符串，由大写和小写英文字母组成。
• $1\leq Q\leq5\times10^5$
• $1\leq t _ i\leq3\ (1\leq i\leq Q)$
• 如果 $t _ i=1$，那么 $1\leq x _ i\leq N\ (1\leq i\leq Q)$。
• $c _ i$ 是一个大写或小写英文字母。
• 如果 $t _ i\neq 1$，那么 $x _ i=0$，$c _ i=$ 'a'。
• $N,Q,t _ i,x _ i$ 都是整数。

输入

输入数据通过标准输入给出，格式如下：

$N$
$S$
$Q$
$t _ 1$ $x _ 1$ $c _ 1$
$t _ 2$ $x _ 2$ $c _ 2$
$\vdots$
$t _ Q$ $x _ Q$ $c _ Q$

输出

在一行中输出答案。

样例输入 1

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

样例输出 1

atcYber

初始时，字符串 $S$ 为 AtCoder。

• 第一次操作将第 $4$ 个字符改为 i，将 $S$ 改为 AtCider。
• 第二次操作将所有小写英文字母改为大写，将 $S$ 改为 ATCIDER。
• 第三次操作将第 $5$ 个字符改为 b，将 $S$ 改为 ATCIbER。
• 第四次操作将所有大写英文字母改为小写，将 $S$ 改为 atciber。
• 第五次操作将第 $4$ 个字符改为 Y，将 $S$ 改为 atcYber。

操作结束后，字符串 $S$ 为 atcYber，所以输出 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