

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
英大文字および英小文字からなる長さ N の文字列 S が与えられます。
これから、文字列 S に対して Q 回の操作を行います。 i 番目 (1\leq i\leq Q) の操作は整数 2 つと文字 1 つからなる組 (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 行で出力せよ。
入力例 1
7 AtCoder 5 1 4 i 3 0 a 1 5 b 2 0 a 1 4 Y
出力例 1
atcYber
はじめ、文字列 S は AtCoder
です。
- 1 番目の操作では、4 文字目を
i
に変更します。変更後の S はAtCider
です。 - 2 番目の操作では、すべての小文字を大文字に変更します。変更後の S は
ATCIDER
です。 - 3 番目の操作では、5 文字目を
b
に変更します。変更後の S はATCIbER
です。 - 4 番目の操作では、すべての大文字を小文字に変更します。変更後の S は
atciber
です。 - 5 番目の操作では、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
Score : 400 points
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 toAtCider
. - 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 toATCIbER
. - 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 toatcYber
.
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