Geohash Grid

Geohash is a way of encoding map coordinates as scalar values so that geographical data can be stored and queried efficiently in databases. In this problem, a map is a $2^n \times 2^n$ grid placed in a standard coordinate system, where the $x$ coordinate grows to the right and the $y$ coordinate grows upward. A map cell is a unit square aligned with the coordinate axes whose lower-left corner is a point with integer coordinates $(x, y)$ such that $0 \le x, y < 2^n$.

A $2^n \times 2^n$ map has $2^{2n}$ cells in total. The geohash $h(c)$ of a map cell $c$ is a $2n$-bit nonnegative integer, built one bit at a time starting from the most significant bit. Set the viewport to the entire map and repeat the following two steps $n$ times:

1. Divide the viewport into two equal parts, the left half and the right half. If cell $c$ is in the left half, the next bit is 0; otherwise it is 1. The half that contains cell $c$ becomes the new viewport.
2. Divide the viewport into two equal parts, the bottom half and the top half. If cell $c$ is in the bottom half, the next bit is 0; otherwise it is 1. The half that contains cell $c$ becomes the new viewport.

A geohash interval $[a, b]$ is the set of cells whose geohash values are between $a$ and $b$, both inclusive. It is often useful to approximate a map region with a few geohash intervals. Given a set of cells $C$ and an integer $t$, an optimal $t$-approximation of $C$ is a region of minimum area that contains $C$ and can be written as a union of at most $t$ geohash intervals. Formally, it is a set $S$ of at most $t$ geohash intervals such that:

• Every cell of $C$ is contained in at least one interval of $S$.
• The number of cells in the union of all intervals of $S$ is as small as possible.

The region $C$ is the set of all cells inside a polygon whose sides are parallel to the grid lines. You are also given $q$ integers $t_1, t_2, \ldots, t_q$. For each $t_k$, find the area of an optimal $t_k$-approximation of $C$, that is, the number of cells in it.

The first line contains an integer $n$ ($1 \le n \le 30$). The side length of the map is $2^n$.

The second line contains an even integer $m$ ($4 \le m \le 200$), the number of vertices of the polygon. The $k$-th of the next $m$ lines contains two integers $x_k$ and $y_k$ ($0 \le x_k, y_k \le 2^n$), the coordinates of one vertex of the polygon. The vertices are given in counterclockwise order. Every side of the polygon is either vertical or horizontal. The polygon does not intersect or touch itself, and no two consecutive sides are parallel.

The next line contains an integer $q$ ($1 \le q \le 100\,000$), the number of queries. The $k$-th of the next $q$ lines contains a single integer $t_k$ ($1 \le t_k \le 10^9$), the $k$-th query.

For each query, print one line. The $k$-th line contains the area of an optimal $t_k$-approximation of the given region.

For the region in the figure, the intervals $[3, 29]$, $[33, 33]$ and $[36, 37]$ form an optimal 3-approximation. The union of the three intervals has area 30.