题目描述

给定一个边均平行于坐标轴的简单多边形。多边形可以不是凸多边形，但不会自交；除了相邻边在公共端点处相交之外，不同边之间没有公共点。

考虑多边形内部以及边界上的所有整数格点，并按字典序排序：先按 $x$ 坐标从小到大排序，若 $x$ 相同，则按 $y$ 坐标从小到大排序。

接下来有若干询问。对于每个询问 $k$，请输出排序后第 $k$ 个整数格点的坐标。排名从 $1$ 开始。

如果多边形内部和边界上的整数格点总数少于 $k$，输出 -1。

输入格式

第一行一个整数 $n_x$，表示横坐标数组的长度。

第二行包含 $n_x$ 个整数 $x_0,x_1,\ldots,x_{n_x-1}$，依次表示多边形各顶点的横坐标。

第三行一个整数 $n_y$，表示纵坐标数组的长度。

第四行包含 $n_y$ 个整数 $y_0,y_1,\ldots,y_{n_y-1}$，依次表示多边形各顶点的纵坐标。

保证 $n_x=n_y=n$，并且 $(x_i,y_i)$ 按逆时针顺序给出多边形的各个顶点。

第五行一个整数 $q$，表示询问数量。

接下来 $q$ 行，每行一个整数 $k$，表示一次询问。

输出格式

第一行输出整数 $q$。

接下来输出 $q$ 行。对于第 $i$ 个询问：

• 如果第 $k_i$ 个整数格点存在，输出两个整数 $x$ 和 $y$，表示其坐标；
• 否则输出 -1。

数据范围

• $4\le n\le 50$；
• $0\le x_i,y_i\le 10^9$；
• 多边形为简单正交多边形，所有顶点互不相同；
• $1\le q\le 50$；
• $1\le k_i\le 10^{18}$。

样例 1

输入

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

输出

9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2