[Solution] Magical Array Codeforces Solution

D. Magical Array

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

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

• Operation 1: Choose two integers i$i$ and j$j$ (2≤i<j≤m−1$2\le i<j\le m-1$), subtract 1$1$ from both ct[i]$c_t[i]$ and ct[j]$c_t[j]$, and add 1$1$ to both ct[i−1]$c_t[i-1]$ and ct[j+1]$c_t[j+1]$. That operation can only be used on a non-special array, that is when t≠k$t\ne k$.;
• Operation 2: Choose two integers i$i$ and j$j$ (2≤i<j≤m−2$2\le i<j\le m-2$), subtract 1$1$ from both ct[i]$c_t[i]$ and ct[j]$c_t[j]$, and add 1$1$ to both ct[i−1]$c_t[i-1]$ and ct[j+2]$c_t[j+2]$. That operation can only be used on a special array, that is when t=k$t=k$.

  Note that Eric can't perform an operation if any element of the array will become less than 0$0$ after that operation.

• of 

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Now, Eric does the following:

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

Lastly, Eric discards the array b$b$.

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

Input

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

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

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

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

It is guaranteed that the sum of n⋅m$n\cdot m$ over all test cases does not exceed 106${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 1018${10}^{18}$, so you can represent it as a 64$64$-bit integer. It can also be shown that the index of the special array is uniquely determined.

In this problem, hacks are disabled.