AT_past202209_n 上からと横から

$ 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} $ と同時に更新する。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ を出力せよ。

### Sample Explanation 1 グリッドは以下のように変化します。 ``` ab cd ``` ``` ab xc ``` ``` yb ac ``` そして、 $ S $ は `dx` となります。よって `dx` を出力します。 ### 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,Q $ は整数である。 - $ a_{i,j} $ は英小文字である。 - 各クエリは問題文に記した $ 2 $ 種類の形式のいずれかである。 - タイプ $ 1 $ のクエリについて、 $ 1 \le p \le H $ であり、 $ p $ は整数である。また、 $ c $ は英小文字である。 - タイプ $ 2 $ のクエリについて、 $ 1 \le p \le W $ であり、 $ p $ は整数である。また、 $ c $ は英小文字である。