/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
縦 H 行、横 W 列のマス目があります。上から i 行目、左から j 列目にあるマスをマス (i, j) と呼びます。
各マスには電球とスイッチが 1 つずつ設置されています。
各マスの電球の初期状態は、長さ W の文字列 S_1, S_2, \dots, S_H によって与えられます。マス (i, j) にある電球は、S_i の j 文字目が 0 のとき消灯、1 のとき点灯しています。
マス (i, j) にあるスイッチを押すと、マス (i, j) およびそのマスと上下左右に隣接するマス（存在するなら）にあるすべての電球の状態が反転します（すなわち、点灯している電球は消灯し、消灯している電球は点灯します）。
高橋君は合計で Q 回、スイッチを押す操作を行います。k 回目 (1 \leq k \leq Q) の操作では、マス (R_k, C_k) にあるスイッチを押します。なお、複数回の操作で同じマスのスイッチが押されることもあります。
すべての操作が終了した後の、各マスの電球の状態を求めてください。
制約
- 1 \leq H \leq 2 \times 10^4
- 1 \leq W
- H \times W \leq 10^6
- S_i は
0および1のみからなる長さ W の文字列 (1 \leq i \leq H) - 1 \leq Q \leq 10^5
- 1 \leq R_k \leq H (1 \leq k \leq Q)
- 1 \leq C_k \leq W (1 \leq k \leq Q)
- H, W, Q, R_k, C_k は整数
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H Q R_1 C_1 R_2 C_2 \vdots R_Q C_Q
出力
すべての操作が終了した後の各マスの電球の状態を H 行で出力せよ。
i 行目 (1 \leq i \leq H) には、長さ W の文字列を出力せよ。この文字列の j 文字目 (1 \leq j \leq W) は、すべての操作が終了した後のマス (i, j) の電球が消灯しているならば 0、点灯しているならば 1 とせよ。
入力例 1
3 3 000 000 000 1 2 2
出力例 1
010 111 010
入力例 2
2 3 010 101 3 1 1 1 1 2 3
出力例 2
011 110
入力例 3
5 6 010110 110001 001110 101010 010101 10 1 1 2 3 3 4 5 2 4 6 1 6 3 1 2 4 4 3 5 5
出力例 3
101001 100110 110101 000011 100011
入力例 4
8 12 101001101001 010110010110 110011001100 001100110011 100100100100 011011011011 111000111000 000111000111 15 1 1 8 12 4 6 5 7 2 10 7 3 1 12 8 1 3 5 6 8 4 6 5 7 3 3 6 10 8 8
出力例 4
011001101110 111100011001 101000001000 000110110011 100100110000 010011101101 000100111101 111111111100
入力例 5
1 1 0 1 1 1
出力例 5
1
Score : 300 pts
Problem Statement
There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Each cell contains one light bulb and one switch.
The initial states of the light bulbs in each cell are given by H strings S_1, S_2, \dots, S_H of length W. The light bulb at cell (i, j) is off if the j-th character of S_i is 0, and on if it is 1.
When the switch at cell (i, j) is pressed, the states of the light bulbs at cell (i, j) and all cells adjacent to it vertically or horizontally (if they exist) are toggled (that is, an on bulb is turned off, and an off bulb is turned on).
Takahashi will perform the operation of pressing a switch a total of Q times. In the k-th operation (1 \leq k \leq Q), he presses the switch at cell (R_k, C_k). Note that the switch in the same cell may be pressed multiple times across different operations.
Find the state of the light bulb in each cell after all operations are completed.
Constraints
- 1 \leq H \leq 2 \times 10^4
- 1 \leq W
- H \times W \leq 10^6
- S_i is a string of length W consisting of
0and1(1 \leq i \leq H). - 1 \leq Q \leq 10^5
- 1 \leq R_k \leq H (1 \leq k \leq Q)
- 1 \leq C_k \leq W (1 \leq k \leq Q)
- H, W, Q, R_k, and C_k are integers.
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H Q R_1 C_1 R_2 C_2 \vdots R_Q C_Q
Output
Print the states of the light bulbs in each cell after all operations are completed in H lines.
The i-th line (1 \leq i \leq H) should contain a string of length W, where the j-th character (1 \leq j \leq W) is 0 if the light bulb at cell (i, j) is off after all operations, and 1 if it is on.
Sample Input 1
3 3 000 000 000 1 2 2
Sample Output 1
010 111 010
Sample Input 2
2 3 010 101 3 1 1 1 1 2 3
Sample Output 2
011 110
Sample Input 3
5 6 010110 110001 001110 101010 010101 10 1 1 2 3 3 4 5 2 4 6 1 6 3 1 2 4 4 3 5 5
Sample Output 3
101001 100110 110101 000011 100011
Sample Input 4
8 12 101001101001 010110010110 110011001100 001100110011 100100100100 011011011011 111000111000 000111000111 15 1 1 8 12 4 6 5 7 2 10 7 3 1 12 8 1 3 5 6 8 4 6 5 7 3 3 6 10 8 8
Sample Output 4
011001101110 111100011001 101000001000 000110110011 100100110000 010011101101 000100111101 111111111100
Sample Input 5
1 1 0 1 1 1
Sample Output 5
1