问题陈述

我们有一个由$H$行从上到下和$W$列从左到右组成的网格。最初，位于从上到下的第$i$行和从左到右的第$j$列的方块上有一个小写英文字母$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$列的交集。
• 将$R_1$、$R_2$、$R_3$和$R_4$中的每个矩形区域旋转$180$度。

这里，网格中矩形区域$R$的$180$度旋转将位于$R$中从上到下的第$i$列和从左到右的第$j$列的字符移动到$R$中从下到上的第$i$列和从右到左的第$j$列上。参见示例的图形。

输出在所有$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

网格的变化如下。