← 返回题目列表

AtCoder · arc153_b

B. 网格旋转

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

分数: 500 点

问题陈述

我们有一个网格 H 从上到下行以及 W 列从左到右。最初,广场位于 i从顶部开始的第行和 j左数第1列有一个小写英文字母 A_{i,j}.

让我们表演一下 Q 在此网格上进行操作。在 i-第次操作,我们得到整数 a_i 和 b_i 这样 1\leq a_i \leq H-1 和 1\leq b_i\leq W-1,并执行以下操作。

  • 让 R_1, R_2, R_3,和 R_4 是网格内的矩形区域,定义如下:
    • R_1 是顶部的交集 a_i 行和最左边 b_i 列;
    • R_2 是顶部的交集 a_i 行和最右边 W-b_i 列;
    • R_3 是底部的交集 H-a_i 行和最左边 b_i 列;
    • R_4 是底部的交集 H-a_i 行和最右边 W-b_i 列。
  • 旋转 180 度各 R_1, R_2, R_3,和 R_4.

这里,一个 180矩形区域的 - 度旋转 R 在网格内移动方块上的字符 i从上往下数第 j从左起第 R 前往广场 i从底部开始第 3 个, j从右数第 R。另请参阅样本的数字。

打印网格 Q 操作。

约束

  • 2\leq H, W,和 HW \leq 5\times 10^5.
  • A_{i,j} 是一个小写英文字母。
  • 1\leq Q\leq 2\times 10^5
  • 1\leq a_i\leq H - 1
  • 1\leq b_i\leq W - 1

输入

输入由标准输入按以下格式给出:

H W
A_{1,1}\cdots A_{1, W}
\vdots
A_{H,1}\cdots A_{H, W}
Q
a_1 b_1
\vdots
a_Q b_Q

输出

按照以下格式打印操作后的网格,其中 B_{i,j} 是方块上的字符 (i,j) 在最后一个网格上。

B_{1,1}\cdots B_{1, W}
\vdots
B_{H,1}\cdots B_{H, W}

示例输入 1

4 5
abcde
fghij
klmno
pqrst
1
3 3

示例输出 1

mlkon
hgfji
cbaed
rqpts

网格将发生如下变化。


示例输入 2

3 7
atcoder
regular
contest
2
1 1
2 5

示例输出 2

testcon
oderatc
ularreg

网格将发生如下变化。


示例输入 3

2 2
ac
wa
3
1 1
1 1
1 1

示例输出 3

ac
wa

网格将发生如下变化。