考虑一个无限的二维平面。平面上有 $n$ 个固定点和一条旋转直线。其中一个点是原点 $(0, 0)$，直线初始时与 $y$ 轴重合。这些点互不相同，但不保证任意三点不共线。

直线正沿逆时针方向旋转。旋转中心始终是给定的 $n$ 个点之一，初始时为原点，但它可能会发生变化。具体来说，只要直线上仅包含一个点，该点就是旋转中心。一旦直线遇到另一个点，考虑当前位于直线上的所有给定点，按坐标 $(x, y)$ 对进行排序。如果直线上有 $k$ 个点，且当前的旋转中心是其中第 $p$ 个（从 1 开始计数），则下一个旋转中心将是这些点中的第 $(k - p + 1)$ 个。如果 $p = k - p + 1$，则旋转中心不改变。初始时，即使直线上有多个给定点，直线也开始旋转。

你的任务是找到第 $q$ 个旋转中心。初始中心编号为 0，只要中心不发生变化，计数器就不会增加。尽管如此，题目保证对于给定的点集，第 $q$ 个旋转中心一定存在。

输入格式

第一行包含一个整数 $n$，表示点的数量 ($2 \le n \le 3000$)。

接下来的 $n$ 行，第 $i$ 行包含两个整数 $x$ 和 $y$，表示第 $i$ 个点的坐标 ($-100 \le x, y \le 100$)。保证其中一个点是 $(0, 0)$。这些点互不相同，但不保证任意三点不共线。

下一行包含一个整数 $Q$，表示查询的数量 ($1 \le Q \le 2700$)。随后有 $Q$ 行，每行包含一个整数 $q_i$ ($0 < q_i \le 10^9$)。保证查询按严格递增顺序给出。

输出格式

输出 $Q$ 行，每行对应一个查询。每行必须包含一对整数：第 $q_i$ 个旋转中心的坐标。

样例

输入 1

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

输出 1

-1 2
1 0
0 0
0 1
2 0
-1 0
0 1

说明

初始旋转中心（编号为 0）是 $(0, 0)$。旋转中心编号 1 是 $(-1, 2)$，因为这是直线最先遇到的点。

然后直线同时遇到两个点 $(0, 1)$ 和 $(1, 0)$，此时直线上共有三个点。$(-1, 2)$ 是排序后这三个点中的第一个，因此中心必须变为第三个点，即 $(1, 0)$。因此，$(1, 0)$ 是旋转中心编号 2。

接着直线遇到三个点 $(1, 0)$、$(0, 0)$ 和 $(2, 0)$，此时直线上共有四个点。中心是排序后这四个点中的第三个，因此中心编号 3 将是这四个点中的第二个，即 $(0, 0)$。

同理，我们可以证明第 4 个旋转中心是 $(0, 1)$。

此后，直线遇到两个点 $(1, 2)$ 和 $(1, 0)$。中心是排序后三个点中的第二个，因此它没有改变。

此后，直线遇到 $(2, 0)$，所以第 5 个旋转中心是 $(2, 0)$。