Furniture Placement on Grid

You are given a room layout represented by an $n\times m$ matrix. Each cell contains either 0 or 1. A 0 denotes that the cell is empty, while a 1 indicates that there is a piece of furniture in that cell. A room layout is defined as good if there exists a path from the top-left cell $(1,1)$ to the bottom-right cell $(n,m)$ using only right and down moves, and the path does not pass through any cell with furniture.

The initial layout is guaranteed to be good. Then, you will be given $Q$ operations. In the $k$-th operation, you try to place a piece of furniture at position $(X_k, Y_k)$. If placing the furniture still leaves the layout good, then the furniture is placed and you should output YES for that operation; otherwise, the placement is cancelled and you should output NO.

Note:

• It is guaranteed that the cell $(X_k,Y_k)$ is not occupied by furniture in the initial layout and has never been occupied in any previous operation.
• Cells $(1,1)$ and $(n,m)$ are always empty.

Path condition in latex: A room configuration is good if $$\exists\; P:\;\{(i,j)\}_{k=1}^{L} \text{ such that } (i,j) \in \{1,\ldots,n\}\times\{1,\ldots,m\},\ (1,1)=(i_1,j_1),\ (n,m)=(i_L,j_L),$$ $$i_{k+1}=i_k \text{ or } j_{k+1}=j_k,\; \text{ and } i_{k+1}\ge i_k,\; j_{k+1}\ge j_k,\; \text{ and } C_{i_k,j_k}=0.$$

inputFormat

The first line contains three integers $n$, $m$, and $Q$.

Then follow $n$ lines, each containing $m$ integers (each either 0 or 1) representing the initial room layout.

Then $Q$ lines follow, each containing two integers $X_k$ and $Y_k$, representing the coordinate where you try to place a furniture.

outputFormat

For each of the $Q$ operations, output a line containing either YES if the furniture was successfully placed, or NO if the placement would violate the goodness of the layout.

sample

3 3 2
0 0 0
0 0 0
0 0 0
2 2
1 2

YES
YES