Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4083
Little Sub and his another Geometry Problem

Time Limit: 3 Seconds      Memory Limit: 262144 KB

Little Sub is happy to see that you solve his geometry problem quickly, so he comes with another geometry problem for you as the reward.

Given a 2-dimensional space described as $\{(x,y)|0 \le x\le M,0\le y\le M\}$ and $N$ points $P_1(x_1,y_1), P_2(x_2,y_2), \dots, P_N(x_N,y_N)$ (note that different points may share the same coordinate), we define a "good square" as a square inside the given 2-dimensional space such that the edges of the square is parallel to the x-axis or the y-axis, and none of the given $N$ points are strictly inside it.

You're also given $Q$ queries. In each query, given a coordinate $(u,v)$, please calculate that the largest area of a good square such that $(u,v)$ is strictly inside.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 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}$), indicating the range of the given 2-dimensional space and the number of the given points.

For the following $N$ lines, the $i$-th line contains two integers $X_i$ and $Y_i$ (${0\le X_i,Y_i\le M}$), indicating the Euclidean coordinate of the $i$-th point.

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$ and $v$(${0\le u,v\le M})$, indicating a query.

Output

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

Sample Input

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

Sample Output

4
9
4

Hint

We now illustrates the second query of the sample input below.

“example”
Author: LIU, Zhengze
Source: ZOJ Monthly, January 2019
Submit    Status