/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 7 点
問題文
高橋君はシューティングゲームで遊んでいます。ゲーム画面は H 行 W 列のグリッドであり、上から i \, (1 \leq i \leq H) 行目、左から j \, (1 \leq j \leq W) のマスを (i, j) と表します。各マスは空マスまたはブロックマスであり、ブロックマスには正の整数で表される色が付けられています。
マス (i, j) の情報は非負整数 S_{i, j} で表されます。S_{i,j} = 0 ならそのマスは空マスであり、S_{i, j} が正の整数ならそのマスは色 S_{i, j} のブロックマスです。
また、H 行目以外に存在するブロックマスであって、下に隣接するマスが空マスであるようなものを空中ブロックと呼びます。はじめ、空中ブロックは存在しません。
高橋君はこれから N 回の操作を行います。i \, (1 \leq i \leq N) 回目の操作は以下の通りです。
- マス (r_i, c_i) を撃つ。そのマスが空マスなら何も起こらず、ブロックマスならそのマスは空マスに変化する。
- その後、全ての空中ブロックが落下する。厳密には、以下の操作を空中ブロックが存在しなくなるまで行う。
- 空中ブロックを一つ選び、そのマスと下に隣接するマスを入れ替える。
N 回の操作が終わった後の各マスの情報を S_{i, j} と同様の方法で出力してください。
制約
- 1 \leq H, W \leq 100
- 0 \leq S_{i, j} \leq 10^9 \, (1 \leq i \leq H, 1 \leq j \leq W)
- S_{i, j} > 0 ならば S_{i + 1, j} > 0 \, (1 \leq i \leq H - 1, 1 \leq j \leq W)
- 1 \leq N \leq 10^3
- 1 \leq r_i \leq H \, (1 \leq i \leq N)
- 1 \leq c_i \leq W \, (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1, 1} \ldots S_{1, W}
\vdots
S_{H, 1} \ldots S_{H, W}
N
r_1 c_1
\vdots
r_N c_N
出力
H 行にわたって出力せよ。各行には W 個の整数を、以下の条件を満たすように空白区切りで出力せよ。
- i \, (1 \leq i \leq H) 行目の j \, (1 \leq j \leq W) 個目の整数は、高橋君の N 回の操作が全て終了した後のマス (i, j) が空マスなら 0 であり、ブロックマスならその色を表す正の整数である。
入力例 1
3 3 0 1 0 1 2 0 3 4 4 1 3 2
出力例 1
0 0 0 1 1 0 3 2 4
マス (3, 2) を撃つと、ゲーム画面は次のように変化します。
0 1 0 \quad 0 1 0 \quad 0 1 0 \quad 0 0 0 1 2 0 \rightarrow 1 2 0 \rightarrow 1 0 0 \rightarrow 1 1 0 3 4 4 \quad 3 0 4 \quad 3 2 4 \quad 3 2 4
入力例 2
1 1 1 1 1 1
出力例 2
0
入力例 3
2 3 18459 0 35959 150312 573935 612940 3 2 3 1 2 1 1
出力例 3
0 0 0 150312 573935 35959
Score : 7 points
Problem Statement
Takahashi is playing with a shooter video game. The game screen has a grid with H horizontal rows and W vertical columns. The square at the i-th (1 \leq i \leq H) row from the top and j-th (1 \leq j \leq W) column from the left in the grid is called (i, j). Each square is either an empty square or a brick square. Each brick square is painted in the color represented by a positive integer.
The state of Square (i, j) is expressed by a non-negative integer S_{i, j}. If S_{i,j} = 0, then the square is an empty square; if S_{i, j} is a positive integer, then the square is a brick square of color S_{i, j}.
Let us call a brick square in the row other than the H-th row from the top a floating brick if the adjacent square below is an empty square. Initially, there is no floating brick.
Now, Takahashi will do N operations, the i-th (1 \leq i \leq N) of which is as follows:
- Shoot Square (r_i, c_i). If the square is an empty square, nothing happens; if it is a brick square, it changes to an empty square.
- Then, all the floating bricks fall. Strictly speaking, the following operation is performed until there is no floating brick:
- Choose one floating brick and swap that square with the adjacent square below.
Print the state of each square after the N operations have finished, in the same format as S_{i, j}.
Constraints
- 1 \leq H, W \leq 100
- 0 \leq S_{i, j} \leq 10^9 \, (1 \leq i \leq H, 1 \leq j \leq W)
- If S_{i, j} > 0, then S_{i + 1, j} > 0 \, (1 \leq i \leq H - 1, 1 \leq j \leq W).
- 1 \leq N \leq 10^3
- 1 \leq r_i \leq H \, (1 \leq i \leq N)
- 1 \leq c_i \leq W \, (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W
S_{1, 1} \ldots S_{1, W}
\vdots
S_{H, 1} \ldots S_{H, W}
N
r_1 c_1
\vdots
r_N c_N
Output
Print H lines. Each line should contain W integers separated by spaces so that the following condition is satisfied:
- The j-th (1 \leq j \leq W) integer in the i-th (1 \leq i \leq H) line should be 0 if Square (i, j) is an empty square after Takahashi's N operations have completed; if it ends up a brick square, it should be the integer representing its color.
Sample Input 1
3 3 0 1 0 1 2 0 3 4 4 1 3 2
Sample Output 1
0 0 0 1 1 0 3 2 4
When he shoots Square (3, 2), the grid transitions as follows:
0 1 0 \quad 0 1 0 \quad 0 1 0 \quad 0 0 0 1 2 0 \rightarrow 1 2 0 \rightarrow 1 0 0 \rightarrow 1 1 0 3 4 4 \quad 3 0 4 \quad 3 2 4 \quad 3 2 4
Sample Input 2
1 1 1 1 1 1
Sample Output 2
0
Sample Input 3
2 3 18459 0 35959 150312 573935 612940 3 2 3 1 2 1 1
Sample Output 3
0 0 0 150312 573935 35959