题目描述

世界末日已经近在眼前。

Midas 星是一颗平面行星，可以将它表示为带有笛卡尔坐标系的无限平面。星球上共有 $Q$ 个聚落。

在第 $0$ 天，Midas 星上出现了感染区域。初始感染区域是一个具有 $N$ 个顶点的凸多边形。感染区域每天会以一种未知的方式扩张，但对于每个编号为 $i>0$ 的日期，都满足以下条件：

1. 如果在第 $i$ 天，某个与初始多边形距离为 $d$ 的点已经被感染，那么所有与初始多边形距离不超过 $d$ 的点也都已被感染；

2. 设第 $k$ 天感染区域的面积为 $S_k$，则

   $$S_i=2S_{i-1}.$$

也就是说，感染区域每天的面积都会变为前一天的两倍。

如果某个聚落落在感染区域内部或边界上，该聚落中的所有生物都会立刻死亡。

对于每个聚落，请求出它被感染的日期（包括第 $0$ 天）。这一天也是该聚落存在的最后一天。

输入格式

第一行输入一个整数 $N$，表示第 $0$ 天感染区域的顶点数：

接下来 $N$ 行，每行输入两个整数 $cx_i,cy_i$，表示感染区域各顶点的坐标。

顶点按逆时针顺序给出，且多边形保证为凸多边形。

随后一行输入一个整数 $Q$，表示聚落数量：

接下来 $Q$ 行，每行输入两个整数 $tx_i,ty_i$，表示一个聚落的坐标。

所有坐标的绝对值均不超过 $10^9$。

保证：

• 给定多边形为凸多边形；
• 顶点按逆时针顺序给出；
• 除第 $0$ 天外，任意聚落到任意一天感染区域边界的距离都不小于 $10^{-6}$。

最后一条保证意味着答案不会落在难以判定的浮点临界位置。

输出格式

按输入顺序输出 $Q$ 个整数，第 $i$ 个整数表示第 $i$ 个聚落被感染的日期。

每个答案单独占一行。

样例

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

0
0
2
4

样例说明

第二个聚落位于初始感染区域的边界上，因此在第 $0$ 天就会被感染。