Magical Array
Description
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.
Input
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
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.
Samples
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
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.