题目描述

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

在 $2^n$ 行 $2^n$ 列的地图上一共有 $2^{2n}$个格子。对于一个格子 $c$，它的地理哈希值 $h(c)$ 是一个 $2n$ 位的非负二进制整数。从最高位开始考虑整个地图，然后重复下面两个步骤 $n$ 次，即可得到 $c$ 的地理哈希值 $h(c)$：

1.把地图分成左右两个面积相等的区域，如果格子 $c$ 在左半边，那么这一位是 $0$，否则是 $1$。然后将考虑范围缩小到 $c$ 所在的那半边地图。

2.把地图分成上下两个面积相等的区域，如果格子 $c$ 在下半边，那么这一位是 $0$，否则是 $1$。然后将考虑范围缩小到 $c$ 所在的那半边地图。

一个“地理哈希区间” $[a,b]$ 表示所有哈希值在 $[a,b]$ 之间的格子。通常应用中，我们会用一些地理哈希区间去近似表示地图。给定一个格子集合 $C$，以及一个正整数 $t$，那么 $C$ 的最优t近似是指使用不超过 $t$ 个地理哈希区间，覆盖住所有 $C$ 中的格子（覆盖其它格子是允许的），同时满足覆盖住的区域的面积最小。

给定一个地图以及一个格子集合 $C$，$C$ 用一个边平行于坐标轴的简单多边形来表示。然后给定 $q$ 个询问$t_1,t_2,\cdots,t_q$，对于每个询问 $t_k$，你需要求出 $C$ 的最优 $t_k$ 近似覆盖住的区域的面积。

输入格式

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

输出格式

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

3 8
1 1
5 1
5 4
3 4
3 8
0 8
0 5
1 5
4 2 3 5 7

32
30
26
24

样例解释

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

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 30$，$0\le x_i,y_i\le 2^n$，$4\le m\le200$，$1\le q\le10^5$，$1\le t_i\le 10^9$。