AT_past202209_n 上からと横から

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.

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.

Print the resulting $ S $ after processing the $ Q $ queries in the order given by the input.

### Sample Explanation 1 The grid transitions as follows: ``` ab cd ``` ``` ab xc ``` ``` yb ac ``` $ S $ results in `dx`, so `dx` should be printed. ### 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.