P3683 [CERC2016] 地理哈希网格 Geohash Grid

“地理哈希”是一个将二维平面坐标编码为整数的过程，这将为数据库中地理数据的存储和查询带来方便。在这个问题中，一个地图是一个建立在标准二维笛卡尔坐标系上的 $2^n$ 行 $2^n$ 列的矩形网格，越往右 $x$ 坐标越大，越往上 $y$ 坐标越大。一个地图格子是一个单位正方形，满足其左下角的点的坐标为 $(x,y)$，其中 $0 \le x,y

第一行包含一个正整数 $n(1 \le n \le 30)$，表示地图的尺寸的以 $2$ 为底的对数。 第二行包含一个正整数 $m(4 \le m \le 200)$，表示多边形顶点的个数。 接下来m行，每行两个整数 $x_i,y_i(0 \le x_i,y_i \le 2^n)$，按逆时针依次表示多边形每个顶点的坐标。 输入数据保证多边形不自交，边平行于坐标轴，且不存在相邻两条边是平行的。 接下来一行包含一个正整数 $q(1 \le q \le 100000)$，表示询问的个数。 接下来 $q$ 行，每行一个正整数 $t_1,t_2,\cdots,t_q(1 \le t_i \le 10^9)$，依次表示每个询问。

输出 $q$ 行，每行一个正整数，依次回答每个询问。

 区间 $[3,29]$、$[33,33]$ 和 $[36,37]$ 组成最优 $3$ 近似，其覆盖住的总面积为 $30$。