分数: 6 点
问题陈述
我们有一个网格 H 水平行和 W 垂直列。 广场位于 i从顶部开始的第行和 j左起第 列有一个小写英文字符 上面写着 a_{i,j} 。此外,我们还有一个空字符串 S.
流程 Q 按照输入给出的顺序查询,并打印结果 S 处理后 Q 查询。
每个查询属于以下两种类型之一。
1 p c:追加字符 a_{p,W} 到字符串的尾部 S。然后,设置 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:追加字符 a_{H,p} 到字符串的尾部 S。然后,设置 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} 是小写英文字符。
- 每个查询都采用问题陈述中指定的两种格式之一。
- 对于每个类型的查询 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 是一个整数。
输出
打印结果 S 处理后 Q 按照输入给出的顺序进行查询。
示例输入 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