Magical Array
Contest: CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1900
Tags: constructive algorithms, hashing, implementation, math

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
3 1
3 10
3 15
3 20
3 25
3 30
1 1378716

Editorial:
First, let's focus on $$$\textbf{operation 1}$$$ and do some calculations:
1. $$$a_{i-1} \times (i-1) + a_i \times i + a_j \times j + a_{j+1} \times (j+1) = i \times (a_{i-1}+a_i) + j \times (a_j+a_{j+1}) -a_{i-1} + a_{j+1}$$$
2. $$$(a_{i-1}+1) \times (i-1) + (a_i-1) \times i + (a_j-1) \times j + (a_{j+1}+1) \times (j+1) $$$ $$$\ \ \ = i \times (a_{i-1}+a_i) + j \times (a_j+a_{j+1}) -a_{i-1} + a_{j+1}$$$
See what? Yes, even if you give lots of $$$\textbf{operation 1}$$$ to array $$$a$$$, the sum of $$$(a_{i} \times i)$$$ remains. Thus, you can easily find $$$c_k$$$.
And how to find the number of $$$\textbf{operation 2}$$$ ? Let's do some calculations again:
1. $$$a_{i-1} \times (i-1) + a_i \times i + a_j \times j + a_{j+1} \times (j+1) +a_{j+2} \times (j+2)$$$ $$$\ \ \ = i \times (a_{i-1}+a_i) + j \times (a_j+a_{j+1}+a_{j+2}) -a_{i-1} + a_{j+1}+2 \times a_{j+2}$$$
2. $$$(a_{i-1}+1) \times (i-1) + (a_i-1) \times i + (a_j-1) \times j + a_{j+1} \times (j+1) + (a_{j+2}+1) \times (j+2)$$$ $$$\ \ \ = i \times (a_{i-1}+a_i) + j \times (a_j+a_{j+1}+a_{j+2}) -a_{i-1} + a_{j+1}+ 2 \times a_{j+2} +1$$$
This operation will add $$$1$$$ to the result of $$$\sum a_i\times i$$$.
Just minus the initial $$$\sum a_i\times i$$$ and you will get the number of operations applied.