D - LOWER Editorial /

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