## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$ 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$ $\left(1\le k\le n\right)$ 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\le i), subtract $1$ from both ${c}_{t}\left[i\right]$ and ${c}_{t}\left[j\right]$, and add $1$ to both ${c}_{t}\left[i-1\right]$ and ${c}_{t}\left[j+1\right]$That operation can only be used on a non-special array, that is when $t\ne k$.;
• Operation 2: Choose two integers $i$ and $j$ ($2\le i), subtract $1$ from both ${c}_{t}\left[i\right]$ and ${c}_{t}\left[j\right]$, and add $1$ to both ${c}_{t}\left[i-1\right]$ and ${c}_{t}\left[j+2\right]$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.

• of
Solution Click Below:-  👉
👇👇👇👇👇

Now, Eric does the following:

• For every non-special array ${c}_{i}$ ($i\ne 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

The first line contains a single integer $t$ ($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$ and $m$ ($3\le n\le {10}^{5}$$7\le m\le 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 $\left[0,{10}^{6}\right]$, and therefore $0\le {c}_{i,j}\le 3\cdot {10}^{11}$ for all possible pairs of $\left(i,j\right)$.

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.