Chessboard Diagonal Moves Parity Challenge

You are given an \(n \times m\) chessboard. The rows are numbered from \(1\) to \(n\) from top to bottom and the columns are numbered from \(1\) to \(m\) from left to right. A cell at row \(x\) and column \(y\) is denoted by \((x,y)\). There are \(c\) pieces placed on the board at distinct positions.

A piece at \((x,y)\) can move to any of the four diagonal cells \((x-1,y-1)\), \((x-1,y+1)\), \((x+1,y-1)\), \((x+1,y+1)\) provided that the destination cell exists on the board and is unoccupied. Note that every move preserves the parity of \(x+y\); that is, if \(x+y\) is even (or odd) initially, it will remain even (or odd) after any number of moves.

You are given \(q\) independent queries. For each query, you are given five integers \(x_1, y_1, x_2, y_2, p\) which define a submatrix with the top-left corner \((x_1,y_1)\) and the bottom-right corner \((x_2,y_2)\). Then, \(p\) positions are provided (each within the submatrix) which specify the cells in the submatrix that must be occupied by a piece in the final configuration. You can move pieces arbitrarily (with no limit on the number of moves) under the movement rules. The goal is to determine whether it is possible to move the pieces so that, within the given submatrix, and only the specified \(p\) positions are occupied by a piece.

Hint: Since moves preserve the parity of \(x+y\), the number of pieces originally on cells of a certain parity can only fill target positions of that same parity. Use a fast I/O method to handle large input sizes.

inputFormat

The first line contains four integers \(n, m, c, q\) \( (1 \leq n,m \leq 10^9,\; 1 \leq c,q \leq 10^5) \) representing the dimensions of the chessboard, the number of pieces, and the number of queries.

The next \(c\) lines each contain two integers \(x\) and \(y\) \( (1 \leq x \leq n,\; 1 \leq y \leq m) \) indicating the positions of the pieces. All positions are distinct.

Then \(q\) queries follow. Each query begins with a line containing five integers \(x_1, y_1, x_2, y_2, p\) \(1 \le x_1 \le x_2 \le n,\; 1 \le y_1 \le y_2 \le m,\; 0 \le p \leq (x_2-x_1+1)\times(y_2-y_1+1)\). This defines the submatrix where the final configuration is to be achieved. The following \(p\) lines each contain two integers \(x\) and \(y\) representing the positions (which lie inside the submatrix) that must be occupied by a piece.

Note: Each query is independent; the board is reset to its initial configuration before every query.

outputFormat

For each query, output a single line containing either YES or NO. Output YES if it is possible to move the pieces so that within the specified submatrix, exactly the given \(p\) positions are occupied by a piece; otherwise, output NO.

sample

4 4 3 3
1 1
2 2
3 4
1 1 3 4 2
1 1
3 4
2 2 4 4 1
4 4
1 1 4 4 3
1 2
2 1
3 4

YES
YES
NO