题目描述

Galina 在一个矩形迷你高尔夫球场练习推杆。球可以视为一个点。

球场的两组边分别沿南北方向和东西方向。一次击球时，球从某个内部点出发，向东北方向运动，速度为 $\sqrt2$ 英寸/秒，也就是说每秒横坐标增加 $1$、纵坐标增加 $1$。

球场完全没有摩擦，因此球会永远保持这个速度。球撞到球场边界时发生完全弹性碰撞。

球场内部有一个池塘，池塘是一个边都与球场边平行的简单多边形。一旦球接触池塘边界，球立即沉入水中。

给定若干个互相独立的起点。对于每个起点，请求出：

• 球第一次接触池塘所经过的时间；
• 接触点的坐标；

或者判断球永远不会碰到池塘。

输入格式

第一行两个整数 $w,h$，表示球场宽和高：

$$4\le w,h\le 5\cdot10^8.$$

球场四个角的坐标分别为

$$(0,0),(w,0),(w,h),(0,h).$$

第二行一个整数 $n$，表示池塘多边形的顶点数：

$$4\le n\le1000.$$

接下来 $n$ 行，每行两个整数 $x_i,y_i$，按遍历顺序给出池塘顶点：

$$1\le x_i\le w-1,\qquad 1\le y_i\le h-1.$$

保证：

• 所有顶点互不相同；
• 顶点均不在球场边界上；
• 每条池塘边均为水平或竖直线段；
• 多边形为简单多边形，没有自交。

接下来一行一个整数 $t$，表示起点数量：

$$1\le t\le100.$$

随后 $t$ 行，每行两个整数 $\tilde x_i,\tilde y_i$：

$$1\le \tilde x_i\le w-1,\qquad 1\le \tilde y_i\le h-1.$$

保证起点不在池塘内部或边界上。

所有起点对应的实验彼此独立。

输出格式

对每个起点输出一行。

如果球永远不会落入池塘，输出：

-1

否则输出三个整数

$$\tau\ x_s\ y_s,$$

其中：

• $\tau>0$ 为球第一次碰到池塘前经过的秒数；
• $(x_s,y_s)$ 为接触点；
• 接触点必须在池塘边界上。

样例

样例 1

10 8
6
1 4
1 5
3 5
3 6
4 6
4 4
4
2 2
1 7
4 7
7 5

2 4 4
3 4 6
13 3 4
15 2 4

样例 2

6 6
4
2 2
4 2
4 4
2 4
3
5 5
5 2
5 5

3 4 4
-1
3 4 4