Geohash 是一种将地图坐标编码为标量值的方法，旨在高效存储和查询数据库中的地理数据。在本题中，地图是一个 $2^n \times 2^n$ 的矩形网格，嵌入在标准坐标系中，其中 $x$ 坐标向右增长，$y$ 坐标向上增长。地图单元格（map cell）是一个与坐标轴对齐的单位正方形，其左下角点的整数坐标 $(x, y)$ 满足 $0 \le x, y < 2^n$。

$2^n \times 2^n$ 的地图共有 $2^{2n}$ 个单元格。给定一个地图单元格 $c$，其 Geohash 值 $h(c)$ 是一个 $2n$ 位的非负整数，通过从最高有效位开始逐位构建。我们将视口（viewport）设置为整个地图，并重复以下两个步骤 $n$ 次：

1. 将视口平分为左右两半。如果单元格 $c$ 在左半部分，则下一位为 $0$，否则为 $1$。新的视口为包含单元格 $c$ 的区域。
2. 将视口平分为上下两半。如果单元格 $c$ 在下半部分，则下一位为 $0$，否则为 $1$。新的视口为包含单元格 $c$ 的区域。

Geohash 区间 $[a, b]$ 是指 Geohash 值在 $a$ 到 $b$ 之间（包含 $a$ 和 $b$）的所有单元格的集合。通常，用一组 Geohash 区间来近似表示地图区域非常有用。给定一组单元格 $C$ 和一个整数 $t$， $C$ 的最优 $t$-近似是指一个包含 $C$ 且能表示为至多 $t$ 个 Geohash 区间并集的最小面积区域。形式上，它是至多 $t$ 个 Geohash 区间的集合 $S$，满足：

• $C$ 中的每个单元格都至少包含在 $S$ 中的一个区间内。
• $S$ 中所有区间的并集所包含的单元格总数尽可能小。

给定一个由边与网格对齐的多边形内部单元格集合所描述的地图区域 $C$。同时给定 $q$ 个目标整数 $t_1, t_2, \dots, t_q$。对于每个 $t_k$，求 $C$ 的最优 $t_k$-近似的面积。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 30$)，即地图维度的二进制对数。

接下来一行包含一个偶数 $m$ ($4 \le m \le 200$)，即多边形的顶点数。

接下来的 $m$ 行中，第 $k$ 行包含两个整数 $x_k$ 和 $y_k$ ($0 \le x_k, y_k \le 2^n$)，表示多边形的一个顶点坐标。顶点按逆时针顺序给出。多边形的每条边要么是垂直的，要么是水平的。你可以假设多边形不会自交或自触，也不包含连续的平行边。

接下来一行包含一个整数 $q$ ($1 \le q \le 100\,000$)，即查询次数。接下来的 $q$ 行中，第 $k$ 行包含一个整数 $t_k$ ($1 \le t_k \le 10^9$)，表示第 $k$ 个查询。

输出格式

第 $k$ 行应包含给定区域的最优 $t_k$-近似的大小。

样例

输入 1

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

输出 1

32
30
26
24

说明 1

在上述示例中，区间 $[3, 29]$、$[33, 33]$ 和 $[36, 37]$ 构成了给定区域的一个最优 3-近似。这三个区间的并集总面积为 30。

Figure 1. Description of what the figure shows