201531: [AtCoder]ARC153 B - Grid Rotations

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

有一个 $H$ 行 $W$ 列的矩阵,矩阵中每个位置都有一个小写字母。每次操作给出 $a,b$,含义是在第 $a,a+1$ 行之间切一刀,再在 $b,b+1$ 列之间切一刀,这样能得到四个矩阵;每个矩阵旋转半周,最后把四个矩阵拼起来得到新矩阵。 有 $n$ 次操作,每次形如 $a_i,b_i$,希望输出操作后的矩阵。

加入题单

上一题 下一题 算法标签: