K. Distinctness Queries
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a matrix with $$$n$$$ rows and $$$m$$$ columns. You will have to answer $$$q$$$ queries of the following type:

  • i1 j1 i2 j2 — in the submatrix whose top-left corner is $$$(i1,j1)$$$ and its bottom-right corner is $$$(i2,j2)$$$, are all of the elements distinct?
Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m,n \cdot m \le 10^5$$$) — the height, and width, of the matrix, respectively.

Each of the next $$$n$$$ lines of input contain $$$m$$$ integers $$$a_{i,1},a_{i,2},\ldots,a_{i,m}$$$ ($$$1 \le a_{i,j} \le n \cdot m$$$) — the elements of the $$$i$$$-th row of the given matrix.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

Each of the following $$$q$$$ lines contain $$$4$$$ integers $$$i_1$$$, $$$j_1$$$, $$$i_2$$$, $$$j_2$$$ ($$$1 \le i_1 \le i_2 \le n$$$, $$$1 \le j_1 \le j_2 \le m$$$) — the submatrix's corner cells' coordinates.

Output

For each query, print "YES", if all of the elements of the given submatrix are distinct, and "NO", otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Examples
Input
2 2
2 1
3 2
9
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2
1 1 1 2
2 1 2 2
1 1 2 1
1 2 2 2
1 1 2 2
Output
YES
YES
YES
YES
YES
YES
YES
YES
NO
Input
4 6
1 4 7 1 2 3
2 5 8 6 5 4
3 6 9 7 8 9
1 2 3 4 5 6
10
1 1 3 3
1 4 3 6
1 1 4 6
1 2 4 3
2 1 3 4
4 1 4 6
1 4 4 4
2 5 4 5
2 1 2 6
4 6 4 6
Output
YES
YES
NO
YES
NO
YES
YES
NO
NO
YES