{"problem":{"name":"Grid Rotations","description":{"content":"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 lett","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc153_b"},"statements":[{"statement_type":"Markdown","content":"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}$.\nLet 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.\n\n*   Let $R_1$, $R_2$, $R_3$, and $R_4$ be rectangular regions within the grid defined as follows:\n    *   $R_1$ is the intersection of the top $a_i$ rows and leftmost $b_i$ columns;\n    *   $R_2$ is the intersection of the top $a_i$ rows and rightmost $W-b_i$ columns;\n    *   $R_3$ is the intersection of the bottom $H-a_i$ rows and leftmost $b_i$ columns;\n    *   $R_4$ is the intersection of the bottom $H-a_i$ rows and rightmost $W-b_i$ columns.\n*   Rotate $180$ degrees each of $R_1$, $R_2$, $R_3$, and $R_4$.\n\nHere, 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.\nPrint the grid after all $Q$ operations.\n\n## Constraints\n\n*   $2\\leq H, W$, and $HW \\leq 5\\times 10^5$.\n*   $A_{i,j}$ is a lowercase English letter.\n*   $1\\leq Q\\leq 2\\times 10^5$\n*   $1\\leq a_i\\leq H - 1$\n*   $1\\leq b_i\\leq W - 1$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$H$ $W$\n$A_{1,1}\\cdots A_{1, W}$\n$\\vdots$\n$A_{H,1}\\cdots A_{H, W}$\n$Q$\n$a_1$ $b_1$\n$\\vdots$\n$a_Q$ $b_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc153_b","tags":[],"sample_group":[["4 5\nabcde\nfghij\nklmno\npqrst\n1\n3 3","mlkon\nhgfji\ncbaed\nrqpts\n\nThe grid will change as follows.\n![image](https://img.atcoder.jp/arc153/5503f0a5f92e488238556b943aa1d6b7.png)"],["3 7\natcoder\nregular\ncontest\n2\n1 1\n2 5","testcon\noderatc\nularreg\n\nThe grid will change as follows.\n![image](https://img.atcoder.jp/arc153/353f0b30a9561e38967fb3aedf5767c5.png)"],["2 2\nac\nwa\n3\n1 1\n1 1\n1 1","ac\nwa\n\nThe grid will change as follows.\n![image](https://img.atcoder.jp/arc153/655a0ac98f0625e806f6abc97853a437.png)"]],"created_at":"2026-03-03 11:01:13"}}