408143: GYM102994 H Yet Another Geometry Problem

There is a $$$2$$$-dimensional plane described as $$$\{(x,y)|0 \leq x\leq M,0\leq y\leq M\}$$$. We also have another $$$N$$$ points $$$P(x_i,y_i)$$$. Different points may share the same coordinates.

We define a good space as a square(in the given plane) with no point strictly inside it. Endpoints of the square should be on integers coordinates.

In each query, given $$$(u,v)$$$, please calculate the largest area of a good space which $$$(u,v)$$$ is strictly inside.

Notice that the border of a legal space has to be parallel to x-axis or y-axis and it should not cross the border of the plane.

There are multiple test cases. The first line of the input contains an integer $$$T$$$($$$T \leq 10$$$), indicating the number of test cases. For each test case:

The first line contains two integers $$$M$$$($$${2\leq M\leq 10^9}$$$) and $$$N$$$($$${0\leq N\leq 5000}$$$).

In the following $$$N$$$ lines, each line contains two integers $$$X_i,Y_i$$$($$${0\le X_i,Y_i\le M}$$$),which denotes the Euclidean coordinate of $$$P(x_i,y_i)$$$.

Then the next line contains one integer $$$Q$$$($$${1\leq Q\leq 5000}$$$), which denotes the number of queries.

In the following $$$Q$$$ lines, each line contains two integers $$$u,v$$$($$${0\le u,v\le M})$$$.

For each query, please output an integer as the answer in one line.

Specially, if there is no legal good space, please output $$$0$$$ instead.

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

4
9
4