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