C. Искатели приключений
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды четверо римских торговцев встретились в одном из римских мансионов, чтобы обсудить свои торговые планы. У торговцев была следующая проблема: торговали они одним и тем же видом товара, поэтому, если они занимались торговлей в одном и том же городе, неизбежно терпели убытки. Было решено распределить города, в которых будет вестись торговля, между собой.

Карту Рима можно в этой задаче представить как плоскость, на которой в некоторых местах отмечены точки — города Римской империи.

Торговцы хотят выбрать некоторую разделяющую точку $$$(x_0, y_0)$$$. Затем в городе с координатами $$$(x_i, y_i)$$$ будет торговать только

  • первый торговец, если $$$x_0 \le x_i$$$ и $$$y_0 \le y_i$$$;
  • второй торговец, если $$$x_0 > x_i$$$ и $$$y_0 \le y_i$$$;
  • третий торговец, если $$$x_0 \le x_i$$$ и $$$y_0 > y_i$$$;
  • четвертый торговец, если $$$x_0 > x_i$$$ и $$$y_0 > y_i$$$.

Торговцы хотят выбрать точку $$$(x_0, y_0)$$$ так, чтобы максимизировать минимальное количество городов, которое достанется кому-либо из них торговцев (то есть максимально честно). Помогите им найти такую точку.

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

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

В первой строке каждого набора входных данных находится одно целое число $$$n$$$ ($$$4 \le n \le 10^5$$$) — количество городов на карте.

Далее идут $$$n$$$ строк, в каждой из которых записаны два целых числа $$$x_i, y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — координаты городов.

Обратите внимание, что некоторые точки могут совпадать. Это связано с тем, что некоторые города могут находиться настолько близко, что их невозможно разделить на карте в заданном масштабе.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

В первой строке выведите одно целое число $$$k$$$ ($$$0 \le k \le \frac{n}{4}$$$) — максимально возможное количество городов, которое достанется каждому торговцу.

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

Пример
Входные данные
4
4
1 1
1 2
2 1
2 2
4
0 0
0 0
0 0
0 0
8
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1
-2 1
-1 2
7
1 1
1 2
1 3
1 4
2 1
3 1
4 1
Выходные данные
1
2 2
0
0 0
2
1 0
0
0 0