AT_past202209_n 上からと横から

给定一个有 $H$ 行 $W$ 列的网格，第 $i$ 行第 $j$ 列的格子上写有一个小写英文字母 $a_{i,j}$。此外，给你一个初始为空的字符串 $S$。 请依次处理 $Q$ 个查询，并在所有查询处理结束后输出最终的 $S$。 每次查询有两种类型之一： - `1 p c`：将第 $p$ 行的第 $W$ 列字符 $a_{p,W}$ 添加到字符串 $S$ 的末尾，然后将本行所有字符整体右移一位，最左端（第 $1$ 列）赋值为 $c$，即 $a_{p,1}=c$，$a_{p,2}=a_{p,1}$，$a_{p,3}=a_{p,2}$，依此类推，最后 $a_{p,W}=a_{p,W-1}$。所有赋值操作同步执行。 - `2 p c`：将第 $H$ 行的第 $p$ 列字符 $a_{H,p}$ 添加到字符串 $S$ 的末尾，然后将本列所有字符整体下移一位，最上端（第 $1$ 行）赋值为 $c$，即 $a_{1,p}=c$，$a_{2,p}=a_{1,p}$，$a_{3,p}=a_{2,p}$，依此类推，最后 $a_{H,p}=a_{H-1,p}$。所有赋值操作同步执行。

输入以如下格式给出： ``` H W Q a_{1,1}a_{1,2}... a_{1,W} a_{2,1}a_{2,2}... a_{2,W} ⋮ a_{H,1}a_{H,2}... a_{H,W} query_1 query_2 ⋮ query_Q ``` 每次查询为如下两种格式之一： ``` t p c ``` 其中 $1 \leq t \leq 2$，$t$、$p$ 均为整数，$c$ 是小写英文字母。

所有 $Q$ 次查询处理完毕后，输出最终得到的字符串 $S$。

### 样例解释 1 网格变化如下： ``` ab cd ``` 经过第一次操作，变成： ``` ab xc ``` 再次变更，变成： ``` yb ac ``` $S$ 变为 `dx`，应输出 `dx`。 ### 数据范围 - $1 \leq H, W \leq 2 \times 10^5$ - $1 \leq H \times W \leq 2 \times 10^5$ - $1 \leq Q \leq 2 \times 10^5$ - $H$、$W$、$Q$ 为整数 - $a_{i,j}$ 是小写英文字母 - 每次查询的格式均为题目所述两种之一 - 对于每个第 $1$ 类查询，$1 \leq p \leq H$，$p$ 是整数，$c$ 是小写英文字母 - 对于每个第 $2$ 类查询，$1 \leq p \leq W$，$p$ 是整数，$c$ 是小写英文字母 由 ChatGPT 5 翻译