\(n\) роботов сбежали из вашей лаборатории! Вам необходимо найти их так быстро, как только возможно, потому что эти роботы являются экспериментальными, и их поведение еще не тестировалось, поэтому они могут быть очень опасны!
К счастью, даже несмотря на то что ваши роботы сбежали, вы все равно имеете над ними некоторый контроль. Во-первых, вы знаете локацию каждого робота: мир, в котором вы живете, может быть представлен в виде бесконечной координатной плоскости, и \(i\)-й робот сейчас находится в точке, имеющей координаты (\(x_i\), \(y_i\)). Более того, вы можете отправить ровно одну команду всем роботам сразу. Команда должна содержать два целых числа \(X\) и \(Y\), и когда каждый робот получит эту команду, он начнет двигаться вперед к точке, имеющей координаты (\(X\), \(Y\)). Робот прекращает движение в двух случаях:
- либо он достиг точки (\(X\), \(Y\));
- либо он не может подойти ближе к точке (\(X\), \(Y\)).
В обычной ситуации все роботы должны уметь передвигаться от одной точки координатной плоскости к любой другой. Каждый робот может выполнять четыре действия для передвижения. Обозначим текущую локацию робота как (\(x_c\), \(y_c\)). Тогда система движения позволяет ему двигаться в любую из четырех соседних точек:
- первое действие позволяет ему двигаться из (\(x_c\), \(y_c\)) в (\(x_c - 1\), \(y_c\));
- второе действие позволяет ему двигаться из (\(x_c\), \(y_c\)) в (\(x_c\), \(y_c + 1\));
- третье действие позволяет ему двигаться из (\(x_c\), \(y_c\)) в (\(x_c + 1\), \(y_c\));
- четвертое действие позволяет ему двигаться из (\(x_c\), \(y_c\)) в (\(x_c\), \(y_c - 1\)).
К сожалению, похоже, что системы движения некоторых роботов работают неисправно. Для каждого робота вы знаете, какие действия он может выполнять, а какие — нет.
Вы хотите отправить команду всем роботам таким образом, чтобы они встретились в одной точке. Чтобы сделать это, вам необходимо выбрать два целых числа \(X\) и \(Y\) такие, что каждый робот может достичь точку (\(X\), \(Y\)). Возможно ли выбрать такую точку?
Выходные данные
Вы должны отвечать на запросы независимо в порядке следования этих запросов во входных данных.
Чтобы ответить на запрос, вам необходимо совершить одно из следующих действий:
- если невозможно найти такую точку, которая достижима всеми \(n\) роботами, выведите одно целое число \(0\) в отдельной строке;
- если возможно найти такую точку, которая достижима всеми \(n\) роботами, в отдельной строке выведите три целых числа, разделенных пробелами: \(1\) \(X\) \(Y\), где \(X\) и \(Y\) — координаты точки, достижимой всеми \(n\) роботами. И \(X\), и \(Y\) должны не превосходить \(10^5\) по абсолютной величине; гарантируется, что если существует хотя бы одна точка, достижимая всеми роботами, то найдется хотя бы одна точка, имеющая обе координаты, не превосходящие \(10^5\) по абсолютной величине.