J. Balancing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On the Ovine Island, you are in charge of a herd of big fat sheeps.

To protect them from big bad wolves, you have arranged them into an $$$n \times m$$$ rectangular pen ($$$n,m \le 2000$$$). Each cell in the pen is either empty (weight $$$0$$$) or contains a sheep with weight $$$g_{i,j},$$$ an integer between $$$[1,10^6]$$$.

Your boss is wondering if there are special properties of the weights of your sheep.

You are given $$$q$$$ queries, each describing a rectangle. For each rectangle, consider all non-empty weights inside it. Determine whether you can choose three different cells in the rectangle such that if their weights are $$$a,b,c$$$, then the largest of them is strictly less than half of their sum: $$$$$$\max(a,b,c) \lt \frac{a+b+c}{2}.$$$$$$

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 2000$$$).

The next $$$n$$$ lines each contain $$$m$$$ integers $$$g_{i,j}$$$ ($$$0 \le g_{i,j} \le 10^6$$$), where $$$g_{i,j}=0$$$ means the cell is empty.

The next line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$).

Each of the next $$$q$$$ lines contains four integers $$$x_1,y_1,x_2,y_2$$$ ($$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$), describing a rectangle with corners $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ (inclusive).

Output

For each query, print YES (case-insensitive) if there exist three different non-empty cells inside the rectangle whose weights satisfy $$$$$$\max(a,b,c) \lt \frac{a+b+c}{2},$$$$$$ and print NO (case-insensitive) otherwise.

Example
Input
3 3
1 0 0
2 3 10
0 4 0
5
1 1 3 3
2 1 2 3
1 1 2 2
2 1 3 2
1 1 1 1
Output
YES
NO
NO
YES
NO
Note

Query 1: 1 1 3 3

This rectangle covers the entire grid. The non-empty weights inside are: $$$\{1,2,3,10,4\}$$$.

We need three different cells with weights $$$a,b,c$$$ such that $$$\max(a,b,c) \lt \frac{a+b+c}{2}.$$$

Choose the triple $$$(2,3,4)$$$. We have $$$\max(2,3,4) = 4$$$ and $$$\frac{2+3+4}{2} = \frac{9}{2} = 4.5$$$.

Since $$$4 \lt 4.5,$$$ the condition holds.

Therefore, the answer for Query 1 is $$$\texttt{YES}$$$.

$$$ $$$

Query 2: 2 1 2 3

This rectangle covers row $$$2$$$ and columns $$$1$$$ through $$$3$$$. The non-empty weights inside are: $$$\{2,3,10\}$$$.

The only possible triple is $$$(2,3,10)$$$. We have $$$\max(2,3,10) = 10$$$ and $$$\frac{2+3+10}{2} = \frac{15}{2} = 7.5$$$.

Since $$$10 \not \lt 7.5$$$, the condition does not hold.

Therefore, the answer for Query 2 is $$$\texttt{NO}$$$.