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

У Эрика есть массив $$$b$$$ длины $$$m$$$, затем он генерирует $$$n$$$ дополнительных массивов $$$c_1, c_2, \dots, c_n$$$, каждый длиной $$$m$$$, из массива $$$b$$$, следующим образом:

Изначально $$$c_i = b$$$ для каждого $$$1 \le i \le n$$$. Эрик тайно выбирает целое число $$$k$$$ $$$(1 \le k \le n)$$$ и выбирает $$$c_k$$$ в качестве специального массива.

Есть две операции, которые Эрик может выполнять над массивом $$$c_t$$$:

  • Операция 1: Выберите два целых числа $$$i$$$ и $$$j$$$ ($$$2 \leq i < j \leq m-1$$$), вычтите $$$1$$$ из $$$c_t[i]$$$ и $$$c_t[j]$$$ и добавьте $$$1$$$ к $$$c_t[i-1]$$$ и $$$c_t[j+1]$$$. Эту операцию можно использовать только с неспециальным массивом, то есть когда $$$t \neq k$$$.;
  • Операция 2: Выберите два целых числа $$$i$$$ и $$$j$$$ ($$$2 \leq i < j \leq m-2$$$), вычтите $$$1$$$ из $$$c_t[i]$$$ и $$$c_t[j]$$$ и добавьте $$$1$$$ к $$$c_t[i-1]$$$ и $$$c_t[j+2]$$$. Эту операцию можно использовать только для специального массива, то есть когда $$$t = k$$$.

    Обратите внимание, что Эрик не может выполнить операцию, если какой-либо элемент массива после этой операции станет меньше $$$0$$$.

Теперь Эрик делает следующее:

  • Для каждого неспециального массива $$$c_i$$$ ($$$i \neq k$$$) Эрик использует только операцию 1 над ним по крайней мере один раз.
  • Для специального массива $$$c_k$$$ Эрик использует над ним только операцию 2 по крайней мере один раз.

Наконец, Эрик отбрасывает массив $$$b$$$.

По заданным массивам $$$c_1, c_2, \dots, c_n$$$ ваша задача найти специальный массив, т.е. значение $$$k$$$. Кроме того, вам нужно найти, сколько раз на нем использовалась операция $$$2$$$.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \leq n \leq 10^5$$$, $$$7 \leq m \leq 3 \cdot 10^5$$$) — количество массивов данных вам, и длина каждого массива.

Следующие $$$n$$$ строк содержат по $$$m$$$ целых чисел, $$$c_{i,1}, c_{i,2}, \dots , c_{i,m}$$$.

Гарантируется, что каждый элемент изначального массива $$$b$$$ находится в диапазоне $$$[0,10^6]$$$, поэтому $$$0 \leq c_{i,j} \leq 3 \cdot 10^{11}$$$ для всех возможных пар $$$(i,j)$$$.

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Гарантируется, что входные данные генерируется в соответствии с описанной выше процедурой.

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

Для каждого набора входных данных выведите одну строку, содержащую два целых числа — индекс специального массива и количество раз, которое над ним выполнялась Операция 2. Можно показать, что при заданных в задаче ограничениях это значение уникально и не превышает $$$10^{18}$$$, поэтому его можно представить в виде $$$64$$$-битного целого числа. Также можно показать, что индекс специального массива определяется однозначно.

В этой задаче взломы отключены.

Пример
Входные данные
7
3 9
0 1 2 0 0 2 1 1 0
0 1 1 1 2 0 0 2 0
0 1 2 0 0 1 2 1 0
3 7
25 15 20 15 25 20 20
26 14 20 14 26 20 20
25 15 20 15 20 20 25
3 9
25 15 20 15 25 20 20 20 20
26 14 20 14 26 20 20 20 20
25 15 20 15 25 15 20 20 25
3 11
25 15 20 15 25 20 20 20 20 20 20
26 14 20 14 26 20 20 20 20 20 20
25 15 20 15 25 20 15 20 20 20 25
3 13
25 15 20 15 25 20 20 20 20 20 20 20 20
26 14 20 14 26 20 20 20 20 20 20 20 20
25 15 20 15 25 20 20 15 20 20 20 20 25
3 15
25 15 20 15 25 20 20 20 20 20 20 20 20 20 20
26 14 20 14 26 20 20 20 20 20 20 20 20 20 20
25 15 20 15 25 20 20 20 15 20 20 20 20 20 25
3 9
909459 479492 676924 224197 162866 164495 193268 742456 728277
948845 455424 731850 327890 304150 237351 251763 225845 798316
975446 401170 792914 272263 300770 242037 236619 334316 725899
Выходные данные
3 1
3 10
3 15
3 20
3 25
3 30
1 1378716
Примечание

В первом наборе входных данных секретный массив $$$b$$$ равен $$$[0, 1, 1, 1, 1, 1, 1, 1, 0]$$$. Массив $$$c_1$$$ и массив $$$c_2$$$ генерируются с использованием операции 1. Массив $$$c_3$$$ генерируется с использованием операции 2.

Для массива $$$c_1$$$ вы можете выбрать $$$i=4$$$ и $$$j=5$$$ и выполнить Операцию 1 один раз, чтобы сгенерировать его. Для массива $$$c_2$$$ вы можете выбрать $$$i=6$$$ и $$$j=7$$$ и выполнить Операцию 1 один раз, чтобы сгенерировать его. Для массива $$$c_3$$$ вы можете выбрать $$$i=4$$$ и $$$j=5$$$ и выполнить Операцию 2 один раз, чтобы сгенерировать его.

Во втором наборе входных данных секретный массив $$$b$$$ равен $$$[20, 20, 20, 20, 20, 20, 20]$$$. Вы также можете обнаружить, что массив $$$c_1$$$ и массив $$$c_2$$$ генерируются с помощью Операции 1. Массив $$$c_3$$$ создается с помощью Операции 2.

В третьем наборе входных данных секретный массив $$$b$$$ равен $$$[20, 20, 20, 20, 20, 20, 20, 20, 20]$$$. Вы также можете обнаружить, что массив $$$c_1$$$ и массив $$$c_2$$$ генерируются с помощью Операции 1. Массив $$$c_3$$$ создается с помощью Операции 2.