/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
縦 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 回すべての操作を行ったとき，操作後のグリッドの状態を出力してください．
制約
- 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
出力
操作後のマス (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
出力例 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
グリッドの状態は次の図のように変化します．
Score : 500 points
Problem Statement
We have a grid with H rows from top to bottom and W columns from left and right. Initially, the square at the i-th row from the top and j-th column from the left has a lowercase English letter A_{i,j}.
Let us perform Q operations on this grid. In the i-th operation, we are given integers a_i and b_i such that 1\leq a_i \leq H-1 and 1\leq b_i\leq W-1, and do the following.
- Let R_1, R_2, R_3, and R_4 be rectangular regions within the grid defined as follows:
- R_1 is the intersection of the top a_i rows and leftmost b_i columns;
- R_2 is the intersection of the top a_i rows and rightmost W-b_i columns;
- R_3 is the intersection of the bottom H-a_i rows and leftmost b_i columns;
- R_4 is the intersection of the bottom H-a_i rows and rightmost W-b_i columns.
- Rotate 180 degrees each of R_1, R_2, R_3, and R_4.
Here, a 180-degree rotation of a rectangular region R within the grid moves the character on the square at the i-th from the top and j-th column from the left in R to the square at the i-th from the bottom and j-th column from the right in R. See also the figures for the samples.
Print the grid after all Q operations.
Constraints
- 2\leq H, W, and HW \leq 5\times 10^5.
- A_{i,j} is a lowercase English letter.
- 1\leq Q\leq 2\times 10^5
- 1\leq a_i\leq H - 1
- 1\leq b_i\leq W - 1
Input
The input is given from Standard Input in the following format:
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
Output
Print the grid after the operations in the following format, where B_{i,j} is the character on the square (i,j) on the final grid.
B_{1,1}\cdots B_{1, W}
\vdots
B_{H,1}\cdots B_{H, W}
Sample Input 1
4 5 abcde fghij klmno pqrst 1 3 3
Sample Output 1
mlkon hgfji cbaed rqpts
The grid will change as follows.
Sample Input 2
3 7 atcoder regular contest 2 1 1 2 5
Sample Output 2
testcon oderatc ularreg
The grid will change as follows.
Sample Input 3
2 2 ac wa 3 1 1 1 1 1 1
Sample Output 3
ac wa
The grid will change as follows.