/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
H 行 W 列のグリッドがあり、i 行 j 列目のマスには英小文字 a_{i,j} が書かれています。また、空の文字列 S があります。
Q 個のクエリを、入力で与えられる順番で処理してください。そして Q 個のクエリを処理した後の S を出力してください。
各クエリは下記の 2 種類のいずれかです。
1 p c:文字列 S の末尾に文字 a_{p,W} を追加する。その後、a_{p,1}=c,a_{p,2}=a_{p,1},a_{p,3}=a_{p,2},\dots,a_{p,W}=a_{p,W-1} と同時に更新する。2 p c:文字列 S の末尾に文字 a_{H,p} を追加する。その後、a_{1,p}=c,a_{2,p}=a_{1,p},a_{3,p}=a_{2,p},\dots,a_{H,p}=a_{H-1,p} と同時に更新する。
制約
- 1 \le H,W \le 2 \times 10^5
- 1 \le H \times W \le 2 \times 10^5
- 1 \le Q \le 2 \times 10^5
- H,W,Q は整数である。
- a_{i,j} は英小文字である。
- 各クエリは問題文に記した 2 種類の形式のいずれかである。
- タイプ 1 のクエリについて、1 \le p \le H であり、p は整数である。また、c は英小文字である。
- タイプ 2 のクエリについて、1 \le p \le W であり、p は整数である。また、c は英小文字である。
入力
入力は以下の形式で標準入力から与えられる。
H\ W\ Q
a_{1,1}a_{1,2}\dots a_{1,W}
a_{2,2}a_{2,2}\dots a_{2,W}
\vdots
a_{H,1}a_{H,2}\dots a_{H,W}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
また、各クエリは以下の形式で与えらえる。
t\ p\ c
ここで、1 \le t \le 2 かつ t は整数である。
出力
Q 個のクエリを入力で与えられる順番で処理した後の S を出力せよ。
入力例 1
2 2 2 ab cd 1 2 x 2 1 y
出力例 1
dx
グリッドは以下のように変化します。
ab cd
ab xc
yb ac
そして、S は dx となります。よって dx を出力します。
入力例 2
3 4 8 abcd defg ghij 1 2 a 1 2 b 1 2 c 1 2 d 2 3 x 2 3 y 2 3 y 2 3 y
出力例 2
gfedibcx
Score : 6 points
Problem Statement
We have a grid with H horizontal rows and W vertical columns. The square at the i-th row from the top and j-th column from the left has a lowercase English character a_{i,j} written on it. Additionally, we have an empty string S.
Process Q queries in the order given by the input, and print the resulting S after processing the Q queries.
Each query is of one of the following two kinds.
1 p c:Append the character a_{p,W} to the tail of the string S. Then, set a_{p,1}=c,a_{p,2}=a_{p,1},a_{p,3}=a_{p,2},\dots,a_{p,W}=a_{p,W-1} simultaneously.2 p c:Append the character a_{H,p} to the tail of the string S. Then, set a_{1,p}=c,a_{2,p}=a_{1,p},a_{3,p}=a_{2,p},\dots,a_{H,p}=a_{H-1,p} simultaneously.
Constraints
- 1 \le H,W \le 2 \times 10^5
- 1 \le H \times W \le 2 \times 10^5
- 1 \le Q \le 2 \times 10^5
- H, W, and Q are integers.
- a_{i,j} is a lowercase English character.
- Each query is in one of the two formats specified in the Problem Statement.
- For each query of type 1, 1 \le p \le H, p is an integer, and c is a lowercase English letter.
- For each query of type 2, 1 \le p \le W, p is an integer, and c is a lowercase English letter.
Input
Input is given from Standard Input in the following format:
H\ W\ Q
a_{1,1}a_{1,2}\dots a_{1,W}
a_{2,2}a_{2,2}\dots a_{2,W}
\vdots
a_{H,1}a_{H,2}\dots a_{H,W}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is given in the following format:
t\ p\ c
Here, 1 \le t \le 2, and t is an integer.
Output
Print the resulting S after processing the Q queries in the order given by the input.
Sample Input 1
2 2 2 ab cd 1 2 x 2 1 y
Sample Output 1
dx
The grid transitions as follows:
ab cd
ab xc
yb ac
S results in dx, so dx should be printed.
Sample Input 2
3 4 8 abcd defg ghij 1 2 a 1 2 b 1 2 c 1 2 d 2 3 x 2 3 y 2 3 y 2 3 y
Sample Output 2
gfedibcx