题目描述

旧扎戈拉市政府决定在城市周围修建一道城墙。城墙的规划已经完成：它将是一条围绕城市的、不自交的 N 边形。现在只剩下确定城墙上的两个入口的位置。

一个入口的可用性定义为：该入口到城市及周边乡村中每一座房屋的距离的平方之和。两点 (x1, y1) 与 (x2, y2) 之间的距离定义为：

sqrt((x1 - x2)^2 + (y1 - y2)^2)

例如，如果某个入口位于 (4, 4)，并且有两座房屋位于 (4, 5) 和 (2, 4)，那么该入口的可用性为：

dist((4,4), (4,5))^2 + dist((4,4), (2,4))^2 = 1^2 + 2^2 = 5

两个入口会把城墙分成长度分别为 A 和 B 的两段。它们应被设置成满足：

1. 两个入口的可用性相等；
2. |A - B| 尽可能小。

你需要编写程序，给出城墙上两个入口的坐标。

输入格式

第一行给出一个正整数 N，表示多边形的顶点数。

接下来 N 行，每行给出两个十进制实数，分别表示构成城墙的多边形顶点的 x 坐标和 y 坐标。顶点按沿多边形某一个方向依次遍历的顺序给出。

下一行给出一个正整数 M，表示房屋数量。

• 如果 M < 10000，则接下来 M 行，每行给出两个十进制实数，表示一座房屋的坐标；
• 如果 M ≥ 10000，则接下来一行给出 a, b, c, d, p。第一座房屋的坐标为 (x1, y1) = (a, b)，之后每一座房屋满足：

(x_{i+1}, y_{i+1}) = ((x_i * c + d) % p, (y_i * d + c) % p)

输出格式

第一行输出两个数，用一个空格分隔，表示其中一个入口的 x 和 y 坐标。

第二行输出另外两个数，表示另一个入口的 x 和 y 坐标。

输出中的四个数都必须保留到小数点后六位。

如果两个入口的可用性分别为 u 和 v，则当满足以下任一条件时，二者会被认为相等：

• |u - v| < 10^{-6}
• |u - v| / u < 10^{-6}

限制

• 3 ≤ N ≤ 10^6
• 1 ≤ M ≤ 10^7
• 0 ≤ x_i, y_i ≤ 10^9
• 0 ≤ a, b, c, d, p ≤ 1000

评分说明

• 在 10% 的测试中，满足“可用性相等且距离最远”的最优解中，两个入口都位于多边形顶点上；并且额外满足 M * N ≤ 10^3
• 另有 20% 的测试中，同样存在顶点上的最优解；并且额外满足 M * N ≤ 10^6
• 再有 30% 的测试中，同样存在顶点上的最优解

示例

输入

4
0 0
0 2
2 2
2 0
1
1 4

输出

0.000000 1.000000
2.000000 1.000000

样例解释

城墙是一个正方形。唯一的一座房屋位于 (1, 4)。

坐标为 (0, 1) 和 (2, 1) 的两个入口，它们的可用性都为：

dist((0,1),(1,4))^2 = dist((2,1),(1,4))^2 = 10

同时它们把城墙分成两段，且 A = B = 4。

因此在这个解中 |A - B| = 0，这已经是最小可能值。
（例如，把入口设在 (0, 0) 和 (2, 0)，它们同样有相等的可用性，但此时 |A - B| = 4。）