JOI '20 Open P1 - Furniture - Olympiads Online Judge

JOI '20 Open P1 - Furniture

Points: 20 (partial)

Time limit: 2.5s

Memory limit: 512M

Problem type

JOI-kun's room is rectangular shaped. It is a grid of $N \times M$ ~N \times M~ blocks. There are $N$ ~N~ horizontal rows. Each row is parallel to the east-west direction. There are $M$ ~M~ vertical columns. Each column is parallel to the south-north direction. The block in the $i$ ~i~-th row from the north and the $j$ ~j~-th column from the west $(1 \le i \le N, 1 \le j \le M)$ ~(1 \le i \le N, 1 \le j \le M)~ is denoted by the block $(i, j)$ ~(i, j)~. Pieces of furniture are located in some of the blocks. For $i, j$ ~i, j~ $(1 \le i \le N, 1 \le j \le M)$ ~(1 \le i \le N, 1 \le j \le M)~, if $C_{i,j} = 1$ ~C_{i,j} = 1~, there is a piece of furniture in the block $(i, j)$ ~(i, j)~. If $C_{i,j} = 0$ ~C_{i,j} = 0~, there is no furniture in the block $(i, j)$ ~(i, j)~.

We say the arrangement of furniture is nice if we can travel from the block $(1, 1)$ ~(1, 1)~ to the block $(N, M)$ ~(N, M)~ without passing through blocks with furniture by repeating travels from one block to another block which is in the south or the east direction. It is guaranteed that the initial arrangement of furniture is nice.

JOI-kun will perform $Q$ ~Q~ operations. The $k$ ~k~-th operation $(1 \le k \le Q)$ ~(1 \le k \le Q)~ will be performed in the following way.

If the arrangement of furniture remains nice if a new piece of furniture is located in the block $(X_k, Y_k)$ ~(X_k, Y_k)~, then he locates a new piece of furniture in the block $(X_k, Y_k)$ ~(X_k, Y_k)~. Otherwise, he performs nothing.

Note that he will not perform an operation to a block where a piece of furniture is located initially, or where he already performed an operation. There is no furniture in the block $(1, 1)$ ~(1, 1)~ and the block $(N, M)$ ~(N, M)~, and he will not perform an operation in these blocks. Write a program which, given the size of the room, the initial arrangement of furniture, and the blocks where he will perform the operations, determines whether a piece of furniture is located or not for each operation.

Input Specification

Read the following data from the standard input. All the values in the input are integers.

$N\ M$ ~N\ M~

$C_{1,1}\ C_{1,2} \dots C_{1,M}$ ~C_{1,1}\ C_{1,2} \dots C_{1,M}~

$C_{2,1}\ C_{2,2} \dots C_{2,M}$ ~C_{2,1}\ C_{2,2} \dots C_{2,M}~

$\vdots$ ~\vdots~

$C_{N,1}\ C_{N,2} \dots C_{N,M}$ ~C_{N,1}\ C_{N,2} \dots C_{N,M}~

$Q$ ~Q~

$X_1\ Y_1$ ~X_1\ Y_1~

$X_2\ Y_2$ ~X_2\ Y_2~

$\vdots$ ~\vdots~

$X_Q\ Y_Q$ ~X_Q\ Y_Q~

Output Specification

Write $Q$ ~Q~ lines to the standard output. The $k$ ~k~-th line $(1 \le k \le Q)$ ~(1 \le k \le Q)~ should contain 1 if JOI-kun locates a new piece of furniture in the block $(X_k, Y_k)$ ~(X_k, Y_k)~ in the $k$ ~k~-th operation. Otherwise, it should contain 0.

Constraints

$1 \le N \le 1\,000$ ~1 \le N \le 1\,000~.
$1 \le M \le 1\,000$ ~1 \le M \le 1\,000~.
$0 \le C_{i,j} \le 1$ ~0 \le C_{i,j} \le 1~ $(1 \le i \le N, 1 \le j \le M)$ ~(1 \le i \le N, 1 \le j \le M)~.
$C_{1,1} = 0$ ~C_{1,1} = 0~.
$C_{N,M} = 0$ ~C_{N,M} = 0~.
The initial arrangement of furniture is nice.
$1 \le Q \le N \times M$ ~1 \le Q \le N \times M~.
$1 \le X_k \le N$ ~1 \le X_k \le N~ $(1 \le k \le Q)$ ~(1 \le k \le Q)~.
$1 \le Y_k \le M$ ~1 \le Y_k \le M~ $(1 \le k \le Q)$ ~(1 \le k \le Q)~.
$(X_k, Y_k) \ne (1, 1)$ ~(X_k, Y_k) \ne (1, 1)~ $(1 \le k \le Q)$ ~(1 \le k \le Q)~.
$(X_k, Y_k) \ne (N, M)$ ~(X_k, Y_k) \ne (N, M)~ $(1 \le k \le Q)$ ~(1 \le k \le Q)~.
$C_{X_k,Y_k} \ne 1$ ~C_{X_k,Y_k} \ne 1~ $(1 \le k \le Q)$ ~(1 \le k \le Q)~.
$(X_k, Y_k) \ne (X_l, Y_l)$ ~(X_k, Y_k) \ne (X_l, Y_l)~ $(1 \le k < l \le Q)$ ~(1 \le k < l \le Q)~.

Subtasks

(5 points) $N \le 100$ ~N \le 100~, $M \le 100$ ~M \le 100~.
(95 points) No additional constraints.

Sample Input 1

Sample Output 1

0
1
0

Explanation for Sample 1

The first operation is performed to the block $(2, 2)$ ~(2, 2)~. If a new piece of furniture is located at the block $(2, 2)$ ~(2, 2)~, then the arrangement will not remain nice. Therefore, JOI-kun does not actually locate a piece of furniture at the block $(2, 2)$ ~(2, 2)~. The output should be $0$ ~0~.

The second operation is performed to the block $(2, 1)$ ~(2, 1)~. If a new piece of furniture is located at the block $(2, 1)$ ~(2, 1)~, we can travel the blocks $(1, 1), (1, 2), (2, 2), (2, 3)$ ~(1, 1), (1, 2), (2, 2), (2, 3)~ in this order, for example, and the arrangement will remain nice. Therefore, JOI-kun locates a new piece of furniture at the block $(2, 1)$ ~(2, 1)~. The output should be $1$ ~1~.

The third operation is performed to the block $(1, 2)$ ~(1, 2)~. Since a piece of furniture is already located at the block $(2, 1)$ ~(2, 1)~, the arrangement will not remain nice if a new piece of furniture is located at the block $(1, 2)$ ~(1, 2)~. Therefore, the output should be $0$ ~0~.

Sample Input 2

Sample Output 2

0
1

Explanation for Sample 2

The first operation is performed to the block $(1, 2)$ ~(1, 2)~. If a new piece of furniture is located at the block $(1, 2)$ ~(1, 2)~, then the arrangement will not remain nice. Therefore, JOI-kun does not actually locate a piece of furniture, and the output should be $0$ ~0~. Note that if we travel the blocks $(1, 1), (2, 1), (2, 2), (2, 3), (1, 3), (1, 4), (1, 5), (2, 5)$ in this order, then we do not pass through blocks with furniture. However, since the travel from the block $(2, 3)$ ~(2, 3)~ to the block $(1, 3)$ ~(1, 3)~ is toward the north direction, it does not satisfy the condition of nice arrangements.

The second operation is performed to the block $(2, 2)$ ~(2, 2)~. If a new piece of furniture is located at the block $(2, 2)$ ~(2, 2)~, then the arrangement will remain nice since we can travel the blocks $(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 5)$ in this order. Therefore, JOI-kun locates a new piece of furniture at the block $(2, 2)$ ~(2, 2)~, and the output should be $1$ ~1~.

Comments

There are no comments at the moment.