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

$$$n$$$ роботов сбежали из вашей лаборатории! Вам необходимо найти их так быстро, как только возможно, потому что эти роботы являются экспериментальными, и их поведение еще не тестировалось, поэтому они могут быть очень опасны!

К счастью, даже несмотря на то что ваши роботы сбежали, вы все равно имеете над ними некоторый контроль. Во-первых, вы знаете локацию каждого робота: мир, в котором вы живете, может быть представлен в виде бесконечной координатной плоскости, и $$$i$$$-й робот сейчас находится в точке, имеющей координаты ($$$x_i$$$, $$$y_i$$$). Более того, вы можете отправить ровно одну команду всем роботам сразу. Команда должна содержать два целых числа $$$X$$$ и $$$Y$$$, и когда каждый робот получит эту команду, он начнет двигаться вперед к точке, имеющей координаты ($$$X$$$, $$$Y$$$). Робот прекращает движение в двух случаях:

  • либо он достиг точки ($$$X$$$, $$$Y$$$);
  • либо он не может подойти ближе к точке ($$$X$$$, $$$Y$$$).

В обычной ситуации все роботы должны уметь передвигаться от одной точки координатной плоскости к любой другой. Каждый робот может выполнять четыре действия для передвижения. Обозначим текущую локацию робота как ($$$x_c$$$, $$$y_c$$$). Тогда система движения позволяет ему двигаться в любую из четырех соседних точек:

  1. первое действие позволяет ему двигаться из ($$$x_c$$$, $$$y_c$$$) в ($$$x_c - 1$$$, $$$y_c$$$);
  2. второе действие позволяет ему двигаться из ($$$x_c$$$, $$$y_c$$$) в ($$$x_c$$$, $$$y_c + 1$$$);
  3. третье действие позволяет ему двигаться из ($$$x_c$$$, $$$y_c$$$) в ($$$x_c + 1$$$, $$$y_c$$$);
  4. четвертое действие позволяет ему двигаться из ($$$x_c$$$, $$$y_c$$$) в ($$$x_c$$$, $$$y_c - 1$$$).

К сожалению, похоже, что системы движения некоторых роботов работают неисправно. Для каждого робота вы знаете, какие действия он может выполнять, а какие — нет.

Вы хотите отправить команду всем роботам таким образом, чтобы они встретились в одной точке. Чтобы сделать это, вам необходимо выбрать два целых числа $$$X$$$ и $$$Y$$$ такие, что каждый робот может достичь точку ($$$X$$$, $$$Y$$$). Возможно ли выбрать такую точку?

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

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов.

Затем следуют $$$q$$$ запросов. Каждый запрос начинается с одной строки, содержащий одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество роботов в запросе. Затем следуют $$$n$$$ строк, $$$i$$$-я из них описывает $$$i$$$-го робота в текущем запросе: она содержит шесть целых чисел $$$x_i$$$, $$$y_i$$$, $$$f_{i, 1}$$$, $$$f_{i, 2}$$$, $$$f_{i, 3}$$$ и $$$f_{i, 4}$$$ ($$$-10^5 \le x_i, y_i \le 10^5$$$, $$$0 \le f_{i, j} \le 1$$$). Первые два числа описывают изначальную локацию $$$i$$$-го робота, а следующие четыре числа описывают, какие действия $$$i$$$-й робот может совершать для передвижения ($$$f_{i, j} = 1$$$, если $$$i$$$-й робот может использовать $$$j$$$-е действие, и $$$f_{i, j} = 0$$$, если он не может использовать $$$j$$$-е действие).

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

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

Вы должны отвечать на запросы независимо в порядке следования этих запросов во входных данных.

Чтобы ответить на запрос, вам необходимо совершить одно из следующих действий:

  • если невозможно найти такую точку, которая достижима всеми $$$n$$$ роботами, выведите одно целое число $$$0$$$ в отдельной строке;
  • если возможно найти такую точку, которая достижима всеми $$$n$$$ роботами, в отдельной строке выведите три целых числа, разделенных пробелами: $$$1$$$ $$$X$$$ $$$Y$$$, где $$$X$$$ и $$$Y$$$ — координаты точки, достижимой всеми $$$n$$$ роботами. И $$$X$$$, и $$$Y$$$ должны не превосходить $$$10^5$$$ по абсолютной величине; гарантируется, что если существует хотя бы одна точка, достижимая всеми роботами, то найдется хотя бы одна точка, имеющая обе координаты, не превосходящие $$$10^5$$$ по абсолютной величине.
Пример
Входные данные
4
2
-1 -2 0 0 0 0
-1 -2 0 0 0 0
3
1 5 1 1 1 1
2 5 0 1 0 1
3 5 1 0 0 0
2
1337 1337 0 1 1 1
1336 1337 1 1 0 1
1
3 5 1 1 1 1
Выходные данные
1 -1 -2
1 2 5
0
1 -100000 -100000