Optimal GeoHash Interval Covering

Given a rectangular grid map of size \(2^n \times 2^n\) (with 0 \(\le\) x,y \(< 2^n\) for the lower‐left corner of each unit cell), each cell is encoded into a \(2n\)-bit nonnegative integer called its GeoHash. The encoding is performed in \(n\) iterations. In each iteration, the current region is first divided vertically into two equal parts. If the cell lies in the left half, output a 0; otherwise, output a 1. Then the region is divided horizontally into two equal parts. If the cell lies in the bottom half, output a 0; otherwise, a 1 is output. Concatenating the \(2n\) bits obtained (from most significant to least significant) yields the GeoHash \(h(c)\) of cell \(c\): \[ h(c)=b_{2n-1}b_{2n-2}\ldots b_0, \] where each bit is determined as described.

A GeoHash interval [a, b] is a contiguous block of GeoHash values (interpreted as integers). Consider a set \(C\) of grid cells (specified by a simple polygon whose edges are parallel to the coordinate axes) and a positive integer \(t\). A \(t\)-approximation of \(C\) is defined as a collection of at most \(t\) GeoHash intervals such that every cell in \(C\) is covered (covering cells outside \(C\) is allowed), and the total area (the number of grid cells in the union of the intervals) is minimized.

You are given the map and the polygon representing \(C\). Then, you are given \(q\) queries; each query provides an integer \(t_k\). For each query, compute the minimal covered area (i.e. the number of grid cells in the union of the chosen intervals) that can be achieved by an optimal \(t_k\)-approximation of \(C\).

inputFormat

The input begins with an integer \(n\) (\(0 < n \le 10\)), which defines the grid as \(2^n \times 2^n\).

The next line contains an integer \(m\), representing the number of vertices of the polygon. Each of the following \(m\) lines contains two integers \(x\) and \(y\), the coordinates of the polygon vertices given in order. The polygon is simple and its edges are parallel to the coordinate axes.

The next line contains an integer \(q\), the number of queries. This is followed by \(q\) lines, each containing a positive integer \(t\) (the maximum number of GeoHash intervals allowed).

outputFormat

For each query, output one line containing a single integer: the minimal area (number of grid cells) covered by an optimal \(t\)-approximation of \(C\).

sample

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

7
2