Codeforces Round 575 (Div. 3) |
---|
Закончено |
$$$n$$$ роботов сбежали из вашей лаборатории! Вам необходимо найти их так быстро, как только возможно, потому что эти роботы являются экспериментальными, и их поведение еще не тестировалось, поэтому они могут быть очень опасны!
К счастью, даже несмотря на то что ваши роботы сбежали, вы все равно имеете над ними некоторый контроль. Во-первых, вы знаете локацию каждого робота: мир, в котором вы живете, может быть представлен в виде бесконечной координатной плоскости, и $$$i$$$-й робот сейчас находится в точке, имеющей координаты ($$$x_i$$$, $$$y_i$$$). Более того, вы можете отправить ровно одну команду всем роботам сразу. Команда должна содержать два целых числа $$$X$$$ и $$$Y$$$, и когда каждый робот получит эту команду, он начнет двигаться вперед к точке, имеющей координаты ($$$X$$$, $$$Y$$$). Робот прекращает движение в двух случаях:
В обычной ситуации все роботы должны уметь передвигаться от одной точки координатной плоскости к любой другой. Каждый робот может выполнять четыре действия для передвижения. Обозначим текущую локацию робота как ($$$x_c$$$, $$$y_c$$$). Тогда система движения позволяет ему двигаться в любую из четырех соседних точек:
К сожалению, похоже, что системы движения некоторых роботов работают неисправно. Для каждого робота вы знаете, какие действия он может выполнять, а какие — нет.
Вы хотите отправить команду всем роботам таким образом, чтобы они встретились в одной точке. Чтобы сделать это, вам необходимо выбрать два целых числа $$$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$$$.
Вы должны отвечать на запросы независимо в порядке следования этих запросов во входных данных.
Чтобы ответить на запрос, вам необходимо совершить одно из следующих действий:
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
Название |
---|