B. Snakes on a Grid
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On a rectangular grid, a snake of size $$$k$$$ is defined to be a subset of cells that is formed by taking the first $$$k$$$ numbered cells in the following figure, where cells are numbered along a path with alternating right and down steps:

Additionally, subsets that are rotations, translations, or reflections of these shapes are also considered snakes. A grid is considered good if every connected component consisting of equal values in the grid is a snake.

Busy Beaver has an $$$N \times M$$$ grid with rows numbered $$$0, \dots, N-1$$$ and columns numbered $$$0, \dots, M-1$$$, where each cell $$$(i, j)$$$ in row $$$i$$$, column $$$j$$$ has a value $$$a_{ij}$$$. Since he's afraid of snakes, he wants you to answer $$$Q$$$ of the following queries: given a contiguous subrectangle of the grid, determine whether or not the subgrid is good.

Input

The first line contains 2 integers, $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 1000$$$) — the dimensions of the grid.

Each of the next $$$N$$$ rows contains $$$M$$$ integers, with the $$$j$$$-th element of the $$$i$$$-th row being $$$a_{i,j}$$$ ($$$1 \leq a_{i, j} \leq 10^6$$$) — the number written in the $$$j$$$-th cell of the $$$i$$$-th row.

The next line contains a single integer, $$$Q$$$ ($$$1 \leq Q \leq 5 \cdot 10^5$$$) — the number of queries.

The next $$$Q$$$ lines describe the queries, Each line contains 4 integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ $$$(0 \leq x_1 \leq x_2 \lt N,$$$ $$$ 0 \leq y_1 \leq y_2 \lt M)$$$, representing a query asking whether the rectangular subgrid with top left corner at $$$(x_1, y_1)$$$ and bottom right corner at $$$(x_2, y_2)$$$ is good.

Output

For each query, output "YES" (without quotes) if the corresponding subgrid consists only of snakes, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Scoring

There are four subtasks for this problem.

  • ($$$15$$$ Points): The sum of the areas of all the queries does not exceed $$$10^6$$$.
  • ($$$15$$$ Points): Every connected component of equal values in the grid has size at most $$$4$$$.
  • ($$$30$$$ Points): Every connected component of equal values in the grid has size at most $$$5$$$.
  • ($$$40$$$ Points): No additional constraints.
Example
Input
10 9
1 1 2 2 3 3 2 2 1
4 1 1 3 3 2 2 4 4
4 4 1 1 2 2 3 4 4
4 2 2 1 1 3 3 4 4
2 2 3 4 4 2 2 3 3
1 1 3 3 4 4 2 2 3
2 1 1 3 3 4 4 2 4
2 2 1 2 4 4 3 3 4
1 3 3 4 4 2 2 3 4
3 3 1 1 1 1 4 4 4
5
0 1 6 5
5 4 7 8
0 6 2 8
6 0 9 3
8 5 9 8
Output
YES
NO
NO
YES
NO
Note

If we color the sample grid with respect to the value in each cell, we get

In the first query, all components are snakes.
In the second query, the component that is not a snake is colored in black.
In the third query, the component that is not a snake is colored in black.
In the fourth query, all components are snakes.
In the fifth query, the component that is not a snake is colored in black.