A15209 | Magical Array

Eric has an array $b$ of length $m$ , then he generates $n$ additional arrays $c_1, c_2, \dots, c_n$ , each of length $m$ , from the array $b$ , by the following way:

Initially, $c_i = b$ for every $1 \le i \le n$ . Eric secretly chooses an integer $k$ $(1 \le k \le n)$ and chooses $c_k$ to be the special array.

There are two operations that Eric can perform on an array $c_t$ :

- Operation 1: Choose two integers $i$ and $j$ ( $2 \leq i < j \leq m-1$ ), subtract $1$ from both $c_t[i]$ and $c_t[j]$ , and add $1$ to both $c_t[i-1]$ and $c_t[j+1]$ . That operation can only be used on a non-special array, that is when $t \neq k$ .;
- Operation 2: Choose two integers $i$ and $j$ ( $2 \leq i < j \leq m-2$ ), subtract $1$ from both $c_t[i]$ and $c_t[j]$ , and add $1$ to both $c_t[i-1]$ and $c_t[j+2]$ . That operation can only be used on a special array, that is when $t = k$ .Note that Eric can't perform an operation if any element of the array will become less than $0$ after that operation.

Now, Eric does the following:

- For every non-special array $c_i$ ( $i \neq k$ ), Eric uses only operation 1 on it at least once.
- For the special array $c_k$ , Eric uses only operation 2 on it at least once.

Lastly, Eric discards the array $b$ .

For given arrays $c_1, c_2, \dots, c_n$ , your task is to find out the special array, i.e. the value $k$ . Also, you need to find the number of times of operation $2$ was used on it.

The first line contains a single integer $t$ ( $1 \leq t \leq 10^4$ ) — the number of test cases. Description of test cases follows.

The first line of each test case contains two integers $n$ and $m$ ( $3 \leq n \leq 10^5$ , $7 \leq m \leq 3 \cdot 10^5$ ) — the number of arrays given to you, and the length of each array.

The next $n$ lines contains $m$ integers each, $c_{i,1}, c_{i,2}, \dots , c_{i,m}$ .

It is guaranteed that each element of the discarded array $b$ is in the range $[0,10^6]$ , and therefore $0 \leq c_{i,j} \leq 3 \cdot 10^{11}$ for all possible pairs of $(i,j)$ .

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$ .

It is guaranteed that the input is generated according to the procedure above.

For each test case, output one line containing two integers — the index of the special array, and the number of times that Operation 2 was performed on it. It can be shown that under the constraints given in the problem, this value is unique and won't exceed $10^{18}$ , so you can represent it as a $64$ -bit integer. It can also be shown that the index of the special array is uniquely determined.

In this problem, hacks are disabled.