Background

RedNebula and JF are playing a game of chess, and then...

Problem Description

There is now an $n \times m$ chessboard. From top to bottom are rows $1 \sim n$, and from left to right are columns $1 \sim m$. A cell in row $x$ and column $y$ is labeled $(x,y)$. There are $c$ chess pieces placed on some cells of the board, with no overlaps. A piece at $(x,y)$ can move to $(x-1,y-1)$, $(x-1,y+1)$, $(x+1,y-1)$, $(x+1,y+1)$ (if these cells exist and have no piece on them).

There are several queries. Each query gives $x_1,y_1,x_2,y_2,p$, and then gives $p$ positions, meaning a submatrix whose top-left corner is $(x_1,y_1)$ and bottom-right corner is $(x_2,y_2)$. Ask whether it is possible to move pieces (with no limit on the number of moves) so that exactly the given $p$ positions inside the submatrix contain pieces. Queries are independent of each other.

To reduce constant factors in time complexity, it is recommended to use faster input methods.

Input Format

The first line contains three positive integers $n,m,c$, representing the number of columns of the board, the number of rows of the board, and the number of existing pieces.

The next $c$ lines each contain two integers $a_i,b_i$, indicating that there is a piece at row $a_i$ and column $b_i$.

The next line contains one positive integer $q$.

Then follow $q$ queries. For each query, the first line contains five positive integers $x_1,y_1,x_2,y_2,p$. The next $p$ lines each contain two positive integers $c_i,d_i$, indicating the positions where you want pieces to be inside the submatrix.

Output Format

For each query, if it is possible to move pieces (with no limit on the number of moves) so that inside the submatrix there are pieces at exactly the given positions, output YES; otherwise output NO.

3 3 5
1 2
1 3
2 1
3 2
3 3
3
1 2 2 3 0
1 2 3 3 4
1 2
1 3
2 3
3 3
1 1 2 3 2
1 3
2 2

NO
YES
NO

Hint

[Sample Explanation #1]

In the explanation, 0 represents an empty cell, and 1 represents a cell with a piece.

Initial state:

011
100
011

For the first query, it can be proven that the piece at $(1,2)$ cannot be moved out of the submatrix from $(1,2)$ to $(2,3)$.

For the second query, consider moving the piece at $(3,2)$ to $(2,3)$, obtaining:

011
101
001

This meets the query requirement. The moving method is not unique.

For the third query, it can be proven that the piece at $(2,1)$ cannot be moved out of the submatrix from $(1,1)$ to $(2,3)$.

[Constraints]

For $25\%$ of the testdata, $n,m,q \le 10$, and $c \le 20$.

For another $25\%$ of the testdata, it is guaranteed that $a_i+b_i\equiv 0 \pmod 2$, and $c_i+d_i\equiv 0 \pmod 2$.

For another $25\%$ of the testdata, it is guaranteed that $n \cdot m - c \le (x_2-x_1+1)\cdot (y_2-y_1+1) - p$.

For $100\%$ of the testdata, $2 \le n,m \le 10^5$, $1 \le c,q \le 10^5$, $c \le n \cdot m$, $1 \le a_i \le n$, $1 \le b_i \le m$, $\sum p \le 2\times 10^5$. For each query, $1 \le p \le (x_2-x_1+1)\cdot (y_2-y_1+1)$, $x_1 \le c_i \le x_2$, $y_1 \le d_i \le y_2$.

[Hints and Notes]

Here is a relatively fast way to read a non-negative integer of type int. Calling read() returns a non-negative integer from the input, and at the same time reads the next character after it.

int read() {
  int x(0);
  char c(getchar());
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return x;
}

Translated by ChatGPT 5