시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 256 MB21150.000%

문제

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

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


예제 출력 1

4
9
4