题目描述

有一个纵向 $H$ 行、横向 $W$ 列的网格。初始时，从上往下第 $i$ 行、从左往右第 $j$ 列的单元格上写有一个英文字母 $A_{i,j}$。

对这个网格进行 $Q$ 次操作。在第 $i$ 次操作中，将给出满足 $1 \leq a_i \leq H-1$, $1 \leq b_i \leq W-1$ 的整数 $a_i$ 和 $b_i$，然后执行以下操作：

• 在网格内定义四个矩形区域 $R_1$, $R_2$, $R_3$, $R_4$，定义如下：
  • 从上往下 $a_i$ 行、从左往右 $b_i$ 列的部分为 $R_1$。
  • 从上往下 $a_i$ 行、从右往左 $W-b_i$ 列的部分为 $R_2$。
  • 从下往上 $H-a_i$ 行、从左往右 $b_i$ 列的部分为 $R_3$。
  • 从下往上 $H-a_i$ 行、从右往左 $W-b_i$ 列的部分为 $R_4$。
• 将 $R_1$, $R_2$, $R_3$, $R_4$ 每个区域分别旋转 $180$ 度。

这里，网格内矩形区域 $R$ 的 $180$ 度旋转是指：将 $R$ 中从上往下第 $i$ 个、从左往右第 $j$ 个单元格上写的字符，移动到 $R$ 中从下往上第 $i$ 个、从右往左第 $j$ 个单元格上。也可以参考输入输出样例中的图示。

在完成全部 $Q$ 次操作后，请输出操作后网格的状态。

输入格式

输入通过标准输入按以下格式给出。

$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$

输出格式

设操作后单元格 $(i,j)$ 上写的字符为 $B_{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

输出

mlkon
hgfji
cbaed
rqpts

样例 2

输入

3 7
atcoder
regular
contest
2
1 1
2 5

输出

testcon
oderatc
ularreg

样例 3

输入

2 2
ac
wa
3
1 1
1 1
1 1

输出

ac
wa

说明/提示

约束条件

• $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$

样例解释 1

网格状态的变化如下图所示。

样例解释 2

网格状态的变化如下图所示。

样例解释 3

网格状态的变化如下图所示。

翻译由 DeepSeek V3 完成