#P18734. [正睿NOI2021训练] 计算几何

[正睿NOI2021训练] 计算几何

计算几何

给定坐标范围为 0≤x,y≤m0\le x,y\le m 的正方形平面区域,以及其中 nn 个整点 Pi=(xi,yi)P_i=(x_i,y_i),这些点可以重合。

称一个正方形区域是“好的”,当且仅当它的四个顶点都是整点、四条边平行于坐标轴、完全位于上述范围内,并且其内部不包含任何给定点。给定点可以落在正方形边界上。

有 QQ 次询问,每次给出一个整点 (u,v)(u,v),求严格包含该点的最大“好的”正方形的面积。严格包含意味着询问点不能位于正方形边界。不存在时输出 00。

输入格式

第一行一个正整数 TT,表示测试数据组数。每组数据依次为:

  1. 一行两个整数 m,nm,n。
  2. 接下来 nn 行,每行两个整数 xi,yix_i,y_i。
  3. 一行一个正整数 QQ。
  4. 接下来 QQ 行,每行两个整数 u,vu,v。

输出格式

每次询问输出一行一个整数,表示最大合法面积。

数据范围

1≤T≤51\le T\le5,2≤m≤1092\le m\le10^9,0≤n≤50000\le n\le5000,1≤Q≤50001\le Q\le5000;所有点与询问坐标均为 [0,m][0,m] 内的整数。

样例 1

输入

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

输出

4

9

4