追捕瑞克·普莱姆

时间限制：2秒
内存限制：256 MB
输入：标准输入
输出：标准输出

瑞克 C-137 和他的莫蒂试图追踪瑞克·普莱姆，为此他们需要在维度之间频繁移动。共有 $n$ 个维度，瑞克·普莱姆可能出现在其中，第 $i$ 个维度在平面维度地图上的坐标为 $(x_i, y_i)$。每个维度还有一个优先级 $p_i$ —— 一个整数，表示瑞克·普莱姆出现在该维度的可能性。

要从地图上坐标为 $(x, y)$ 的点到达维度 $i$，瑞克和莫蒂需要花费 $\max(|x - x_i|, |y - y_i|)$ 的时间。由于最初未知瑞克·普莱姆会在哪个维度被找到，当前的目标是选择一个位置，使得从该位置到任意 $n$ 个维度的时间（考虑优先级）尽可能快。

形式化地，需要找到 $x$ 和 $y$，使得

$$ \sum_{i=1}^n p_i \cdot \max(|x - x_i|, |y - y_i|) $$

最小。

请帮助瑞克和莫蒂确定这样的点 $(x, y)$。该点可以是地图上具有整数或半整数坐标的任意点，不一定与给定的 $n$ 个维度之一重合。

输入格式

第一行包含一个整数 $n$ —— 考虑的维度数量 ($1 \le n \le 2 \cdot 10^5$)。
第二行包含 $n$ 个整数 $p_i$ —— 维度的优先级 ($1 \le p_i \le 10^6$)。
接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ —— 第 $i$ 个维度的坐标 ($|x_i|, |y_i| \le 10^6$)。

输出格式

输出两个整数 $2x$ 和 $2y$ —— 两倍的坐标，即瑞克和莫蒂应该选择的位置。如果有多个点使得目标函数最小，输出其中任意一个。

样例

输入

4
1 1 1 3
-2 -2
-2 2
2 -2
2 2

输出

0 0

输入

5
2 1 1 3 4
0 1
19 6
17 21
17 21
7 10

输出

14 20