Погоня за Риком Праймом
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рик C-137 и его Морти пытаются выследить Рика Прайма, и для этого им приходится много перемещаться между измерениями. Всего есть $$$n$$$ измерений, в которых Рик Прайм может находиться, и $$$i$$$-е измерение на плоской карте измерений находится в точке с координатами $$$(x_i, y_i)$$$. Также у каждого измерения есть свой приоритет $$$p_i$$$ — целое число, задающее, насколько вероятно появление в нем Рика Прайма.

Чтобы попасть из точки на карте с координатами $$$(x, y)$$$ в измерение $$$i$$$, Рику и Морти потребуется $$$\max(|x - x_i|, |y - y_i|)$$$ времени. Поскольку изначально неизвестно, в каком измерении будет обнаружен Рик Прайм, текущая цель — расположиться в такой точке, от которой быстрее всего можно добраться до любого из $$$n$$$ измерений с учетом приоритетов.

Формально, требуется найти такие $$$x$$$ и $$$y$$$, при которых величина $$$$$$\sum\limits_{i=1}^n p_i \cdot \max(|x - x_i|, |y - y_i|)$$$$$$ минимальна.

Помогите Рику и Морти определить такую точку $$$(x, y)$$$. Точка $$$(x, y)$$$ при этом может быть любой точкой на карте с целыми или полуцелыми координатами, не обязательно совпадающей с одним из $$$n$$$ данных измерений.

Входные данные

В первой строке ввода дано целое число $$$n$$$ — количество рассматриваемых измерений ($$$1 \le n \le 2 \cdot 10^5$$$).

Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$p_i$$$ — приоритеты измерений ($$$1 \le p_i \le 10^6$$$).

В $$$i$$$-й из следующих $$$n$$$ строк через пробел даны два целых числа $$$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