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

Cirno дала AquaMoon задачу. Есть $$$m$$$ человек, пронумерованных целыми числами от $$$0$$$ до $$$m - 1$$$. Они стоят на координатной прямой в точках с положительными целочисленными координатами. Они смотрят в направлении увеличения координат.

В этот момент все начинают бежать с фиксированной скоростью в направлении увеличения координат. Изначальная координата $$$i$$$-о человека на прямой это $$$x_i$$$, а скорость $$$i$$$-о человека это $$$v_i$$$. Поэтому координата $$$i$$$-о человека в момент времени $$$t$$$ будет $$$x_i + t \cdot v_i$$$.

Cirno запомнила координаты всех $$$m$$$ человек в $$$k$$$ последовательных целочисленных моментах времени от $$$0$$$ до $$$k - 1$$$. В каждый момент координаты всех $$$m$$$ человек были запомнены в произвольном порядке.

Чтобы сделать задачу более веселой, Cirno изменила одну из координат в момент времени $$$y$$$ ($$$0 < y < k-1$$$) на другое целое число.

AquaMoon хочет найти момент времени $$$y$$$ и изначальную координату $$$p$$$ перед изменением. К сожалению, она совсем не программист. Поэтому она не смогла решить эту задачу. Можете ли вы помочь ей?

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

Эта задача сделана как интерактивная. Это означает, что ваше решение будет считывать входные данные, которые вывел интерактор. Однако, интерактор выведет полные входные данные в начале, и после этого вы должны будете вывести ответ. Поэтому вы должны решать задачу так, как если бы вы решали обычную, не интерактивную задачу, потому что у вас не будет никакого процесса взаимодействия. Единственная вещь, про которую вы не должны забыть — это сбросить буфер выходного потока после вывода ответа. Иначе ваше решение может получить вердикт «Решение «зависло»». Обратитесь к руководству по интерактивным задачам для более детальной информации про сброс буфера выходного потока.

В первой строке находится два целых числа $$$m$$$ и $$$k$$$ ($$$5 \leq m \leq 1000$$$, $$$7 \leq k \leq 1000$$$) — количество человек и количество запомненных моментов.

Следующие $$$k$$$ строк содержат запомненные координаты. $$$i$$$-я из этих строк содержит $$$m$$$ целых чисел от $$$1$$$ до $$$10^6$$$ (включительно), обозначающих координаты, которые запомнила Cirno в момент времени $$$i-1$$$.

Гарантируется, что входные данные валидные (то есть только одно целое число было изменено на другое в соответствии с условием задачи). Также гарантируется, что $$$1 \le v_i \le 1000$$$ для всех $$$1 \leq i \leq m$$$.

Формат теста для взлома:

В первой строке должно находиться два целых числа $$$m$$$ и $$$k$$$ ($$$5 \leq m \leq 1000$$$, $$$7 \leq k \leq 1000$$$) — количество человек и количество запомненных моментов.

Во второй строке должно находиться $$$m$$$ целых чисел $$$x_0, x_1, \dots,x_{m - 1}$$$ ($$$1 \le x_i \le 10^6$$$), где $$$x_i$$$ это изначальная координата $$$i$$$-о человека.

В третьей строке должно находиться $$$m$$$ целых чисел $$$v_0, v_1, \dots,v_{m - 1}$$$ ($$$1 \le v_i \le 1000$$$), где $$$v_i$$$ это скорость $$$i$$$-о человека. Должно быть выполнено, что $$$x_i + (k-1) v_i \leq 10^6$$$ для всех $$$0 \leq i < m$$$.

Каждая из следующих $$$k$$$ строк должна содержать $$$m$$$ целых чисел. $$$i$$$-я строка должна содержать $$$m$$$ различных целых чисел $$$p_0, p_1, \ldots, p_{m-1}$$$ ($$$0 \leq p_j < m$$$). Их значение: $$$j$$$-е целое число во входных данных в момент времени $$$i$$$ это координата человека $$$p_{j}$$$.

В последней строке должно находиться три целых числа $$$y$$$, $$$i$$$, $$$c$$$. Cirno поменяла координату $$$i$$$-о человека в момент времени $$$y$$$ на $$$c$$$ ($$$1 \leq y \leq k-2$$$, $$$0 \leq i \leq m - 1$$$, $$$1 \leq c \leq 10^6$$$, $$$c \neq x_i + y \cdot v_i$$$).

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

Выведите единственную строку с двумя целыми числами $$$y$$$, $$$p$$$ — момент времени, который содержит измененную координату и изначальная координата.

Пример
Входные данные
5 7
6 9 9 6 9
10 7 10 8 10
11 11 11 10 8
12 12 12 12 9
14 13 12 10 13
11 14 16 14 14
12 15 18 15 15
Выходные данные
4 13
Примечание

В первом тесте изначальные координаты людей это $$$9$$$, $$$6$$$, $$$6$$$, $$$9$$$, $$$9$$$ и их скорости это $$$1$$$, $$$2$$$, $$$1$$$, $$$1$$$, $$$1$$$. Поэтому несложно заметить, что в момент времени $$$4$$$ одна координата была изменена c $$$13$$$ на $$$12$$$.

Это первый тест, записанный в формате для взломов:


5 7
9 6 6 9 9
1 2 1 1 1
2 3 4 1 0
0 2 3 1 4
4 3 0 1 2
1 3 4 0 2
1 4 0 2 3
2 4 1 3 0
2 4 1 3 0
4 0 12