D. Удивительные лампочки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы гордый владелец бесконечно большой сетки лампочек, представленной в Декартовой системе координат. Изначально все лампочки выключены, за исключением одной лампочки, в которой вы спрятали свое самое ценное сокровище.

Чтобы скрыть местоположение вашего сокровища, вы выполняете следующую операцию произвольное количество раз (возможно, ноль):

  • Выберите два целых числа $$$x$$$ и $$$y$$$, и переключите состояние $$$4$$$ лампочек в точках $$$(x, y)$$$, $$$(x, y + 1)$$$, $$$(x + 1, y - 1)$$$ и $$$(x + 1, y)$$$. Другими словами, для каждой лампочки включите её, если она была выключена, и выключите её, если она была включена. Обратите внимание, что нет ограничений на $$$x$$$ и $$$y$$$.

В конце концов, $$$n$$$ лампочек включены в координатах $$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$. К сожалению, вы уже забыли, где спрятали свое сокровище, поэтому теперь вам нужно выяснить одно возможное местоположение сокровища. Удачи!

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество лампочек, которые включены.

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$\color{red}{-10^8} \le x_i, y_i \le \color{red}{10^8}$$$) — координаты $$$i$$$-й лампочки. Гарантируется, что все координаты различны.

Дополнительное ограничение: Существует хотя бы одно положение $$$(s, t)$$$ ($$$\color{red}{-10^9} \le s, t \le \color{red}{10^9}$$$), такое что, если лампочка в позиции $$$(s, t)$$$ изначально включена, то после выполнения произвольного количества операций (возможно, ноль) мы получим данную конфигурацию лампочек.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$.

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

Для каждого тестового случая выведите два целых числа $$$s$$$ и $$$t$$$ ($$$-10^9 \le s, t \le 10^9$$$) — одно возможное местоположение похороненного сокровища. Если существует несколько решений, выведите любое из них.

Для этой задачи взломы отключены.

Пример
Входные данные
4
1
2 3
3
-2 -1
-1 -2
-1 -3
7
7 26
6 27
6 28
7 27
8 26
8 27
7 28
11
70 9
69 8
69 0
73 5
70 -1
70 5
71 7
70 4
73 4
71 3
72 3
Выходные данные
2 3
-2 -2
7 27
72 7
Примечание

Для первого набора входных данных одно возможное положение, где вы спрятали свое сокровище, это $$$(2, 3)$$$. Затем вы не выполняли никаких операций.

В конце концов, только лампочка в $$$(2, 3)$$$ включена.

Для второго набора одно возможное положение, где вы спрятали свое сокровище, это $$$(-2, -2)$$$. Затем вы выполнили $$$1$$$ операцию с $$$x = -2$$$, $$$y = -2$$$.

Операция переключает состояние $$$4$$$ лампочек в $$$(-2, -2)$$$, $$$(-2, -1)$$$, $$$(-1, -3)$$$ и $$$(-1, -2)$$$.

В конце концов, лампочки в $$$(-2, -1)$$$, $$$(-1, -2)$$$ и $$$(-1, -3)$$$ включены.