Петя пришел на урок информатики. На этом уроке обсуждали новую тему: геометрию. Причем не простая, а гробовая геометрия. Пете было лень решать одну из задач, которую ему дали, и как всегда, он попросил вас ему помочь.
Но в этот раз вы решили сказать, что не поможете. Петя же сказал, что если вы не поможете, то он даст вам гробовую задачу на стереометрию. А вряд ли кто захочет такое решать. Поэтому вы решили все-таки помочь с задачей на геометрию. Задача звучит так:
Дано $$$n$$$ целочисленных точек на плоскости, где $$$i$$$-ая точка имеет вид $$$(x_i, y_i)$$$. Также загадана одна дополнительная точка, пусть она имеет вид $$$(a, b)$$$. Дополнительно, вам дан массив $$$d$$$ размера $$$n$$$, который представляет из себя перемешанный список целочисленных квадратов расстояний от точки $$$(a, b)$$$ до всех точек $$$(x_i, y_i)$$$ для $$$1 \le i \le n$$$. То есть, каждому элементу списка $$$d$$$ мы можем сопоставить точку $$$(x_i, y_i)$$$ из списка изначальных точек, причем данный элемент будет равен квадрату расстояния между этой точкой и $$$(a, b)$$$, и каждая точка сопоставляется ровно одному элементу списка $$$d$$$.
Вам необходимо по всем данным восстановить любую такую целочисленную точку $$$(a, b)$$$, для которой выполняется условие $$$-5 \cdot 10^8 \le a, b \le 5 \cdot 10^8$$$. Причем сделать это надо для $$$t$$$ наборов, потому что одноклассники Пети попросили вас тоже решить задачу.
На ввод в первой строке подается число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество тестов.
В каждом тесте в первой строке вводится число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество точек на плоскости.
Затем в каждом тесте в следующих $$$n$$$ строках вводятся точки на плоскости $$$x_i, y_i$$$ ($$$|x|, |y| \le 5 \cdot 10^8$$$) — координаты $$$i$$$-ой точки.
И в $$$n + 2$$$-ой строке вводится массив целых чисел $$$d$$$ ($$$0 \le d_i \le 2 \cdot 10^{18}$$$).
Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$10^5$$$. Также гарантируется, что во всех тестах, за исключением примера, точки сгенерированы равновероятно.
Для каждого теста выведите подходящую целочисленную точку $$$(a, b)$$$, для которой выполняется условие $$$-5 \cdot 10^8 \le a, b \le 5 \cdot 10^8$$$. Если ответов существует несколько, то выведите любой. Гарантируется, что ответ существует.
В данной задаче $$$50$$$ тестов, каждый из которых оценивается в $$$2$$$ балла. Гарантируется, что существуют $$$10$$$ тестов, где для всех точек $$$|x|, |y| \le 10$$$, $$$t \le 100$$$ (существует ответ $$$(a, b)$$$ такой, что $$$-10 \le a, b \le 10$$$), а также существуют другие $$$20$$$ тестов, где сумма $$$n$$$ во всем тестам до $$$100$$$. Все тесты оцениваются независимо.
В этих $$$10$$$ тестах точки генерируются равновероятно в диапазоне $$$(-10, 10)$$$, в остальных — в диапазоне $$$(-5 \cdot 10^8, 5 \cdot 10^8)$$$.
1 4 5 1 -1 5 1 1 4 6 10 8 8 20
3 3
Иллюстрация к примеру. Точка $$$A$$$ — ответ
