← 返回题目列表

AtCoder · past202209_n

N. 从上方和侧面

中文机器翻译题面 查看原题

分数: 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