지오해시 격자

지오해시(geohash)는 지도 좌표를 스칼라 값으로 부호화하는 방법으로, 데이터베이스에서 지리 데이터를 효율적으로 저장하고 조회하는 데 쓰인다. 이 문제에서 지도는 표준 좌표계 위에 놓인 $2^n \times 2^n$ 크기의 격자이다. $x$ 좌표는 오른쪽으로 갈수록, $y$ 좌표는 위쪽으로 갈수록 커진다. 지도의 칸은 좌표축에 평행한 단위 정사각형이며, 왼쪽 아래 꼭짓점이 $0 \le x, y < 2^n$을 만족하는 정수 좌표 $(x, y)$이다.

$2^n \times 2^n$ 지도에는 모두 $2^{2n}$개의 칸이 있다. 칸 $c$의 지오해시 $h(c)$는 $2n$비트의 음이 아닌 정수이고, 최상위 비트부터 한 비트씩 정한다. 처음에 보기 영역을 지도 전체로 두고 다음 두 단계를 $n$번 반복한다.

1. 보기 영역을 왼쪽 절반과 오른쪽 절반으로 똑같이 나눈다. 칸 $c$가 왼쪽 절반에 있으면 다음 비트는 0이고, 아니면 1이다. 칸 $c$가 들어 있는 절반이 새 보기 영역이 된다.
2. 보기 영역을 아래쪽 절반과 위쪽 절반으로 똑같이 나눈다. 칸 $c$가 아래쪽 절반에 있으면 다음 비트는 0이고, 아니면 1이다. 칸 $c$가 들어 있는 절반이 새 보기 영역이 된다.

지오해시 구간 $[a, b]$는 지오해시 값이 $a$ 이상 $b$ 이하인 칸의 집합이다. 지도의 영역을 지오해시 구간 몇 개로 근사하면 편리할 때가 많다. 칸의 집합 $C$와 정수 $t$가 주어질 때, $C$의 최적 $t$-근사는 $C$를 포함하고 지오해시 구간 최대 $t$개의 합집합으로 나타낼 수 있는 영역 가운데 넓이가 가장 작은 것이다. 엄밀하게는 지오해시 구간 최대 $t$개로 이루어진 집합 $S$ 가운데 다음 조건을 만족하는 것이다.

• $C$의 모든 칸이 $S$의 구간 중 적어도 하나에 들어 있다.
• $S$에 속한 모든 구간의 합집합에 들어 있는 칸의 수가 가능한 한 작다.

영역 $C$는 변이 격자와 평행한 다각형의 내부에 있는 칸 전체로 주어진다. 정수 $q$개 $t_1, t_2, \ldots, t_q$도 주어진다. 각 $t_k$에 대해 $C$의 최적 $t_k$-근사의 넓이, 즉 그 영역에 들어 있는 칸의 수를 구하시오.

첫째 줄에 정수 $n$ ($1 \le n \le 30$)이 주어진다. 지도 한 변의 길이는 $2^n$이다.

둘째 줄에 다각형의 꼭짓점 수인 짝수 $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$번째 줄에는 $k$번째 질의인 정수 $t_k$ ($1 \le t_k \le 10^9$)가 주어진다.

$k$번째 줄에 주어진 영역의 최적 $t_k$-근사의 넓이를 출력한다.

그림의 영역에서 구간 $[3, 29]$, $[33, 33]$, $[36, 37]$은 최적 3-근사를 이룬다. 세 구간의 합집합의 넓이는 30이다.