또 다른 기하 문제

2차원 평면 $\{(x,y) \mid 0 \leq x \leq M, 0 \leq y \leq M\}$이 주어진다. 이 평면 위에 $N$개의 점 $P(x_i, y_i)$가 있다. 서로 다른 점이 같은 좌표를 가질 수 있다.

경계를 제외한 내부에 점이 하나도 없는 정사각형을 좋은 공간이라고 정의한다. 정사각형의 꼭짓점은 정수 좌표에 있어야 한다.

각 질의 $(u,v)$에 대해, $(u,v)$가 경계를 제외한 내부에 놓이는 좋은 공간 중 넓이가 가장 큰 것의 넓이를 구한다.

정사각형의 변은 x축 또는 y축과 평행해야 하며, 평면의 경계를 넘어서는 안 된다.

입력의 첫 줄에 테스트 케이스의 수 $T$($T \leq 10$)가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 정수 $M$($2 \leq M \leq 10^9$)과 $N$($0 \leq N \leq 5000$)이 주어진다.

이어지는 $N$개의 줄에는 각각 정수 $X_i, Y_i$($0 \leq X_i, Y_i \leq M$)가 주어지며, 이는 점 $P(x_i, y_i)$의 유클리드 좌표이다.

이어지는 줄에는 질의의 수 $Q$($1 \leq Q \leq 5000$)가 주어진다.

이어지는 $Q$개의 줄에는 각각 정수 $u, v$($0 \leq u, v \leq M$)가 주어진다.

각 질의에 대해 답을 한 줄에 하나씩 출력한다. 좋은 공간이 존재하지 않으면 0을 출력한다.