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.

In the first test case, the secret array $b$ is $[0, 1, 1, 1, 1, 1, 1, 1, 0]$ . Array $c_1$ and array $c_2$ are generated by using operation 1. Array $c_3$ is generated by using operation 2.

For Array $c_1$ ,you can choose $i=4$ and $j=5$ perform Operation 1 one time to generate it. For Array $c_2$ , you can choose $i=6$ and $j=7$ perform Operation 1 one time to generate it. For Array $c_3$ ,you can choose $i=4$ and $j=5$ perform Operation 2 one time to generate it.

In the second test case, the secret array $b$ is $[20, 20, 20, 20, 20, 20, 20]$ . You can also find that array $c_1$ and array $c_2$ are generated by using Operation 1. Array $c_3$ is generated by using Operation 2.

In the third test case, the secret array $b$ is $[20, 20, 20, 20, 20, 20, 20, 20, 20]$ . You can also find that array $c_1$ and array $c_2$ are generated by using Operation 1. Array $c_3$ is generated by using Operation 2.