CF1704D.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 \lt 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 \lt 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.

Eric 有一个长度为 $m$ 的数组 $b$，然后他基于数组 $b$ 生成了 $n$ 个额外的数组 $c_1, c_2, \dots, c_n$，每个长度均为 $m$，具体方式如下：

初始时，对每个 $1 \le i \le n$，令 $c_i = b$。Eric 秘密选择一个整数 $k$（满足 $1 \le k \le n$），并将 $c_k$ 设为特殊数组。

Eric 可以对任意数组 $c_t$ 执行以下两种操作之一：

• 操作 1：选择两个整数 $i$ 和 $j$（满足 $2 \leq i \lt j \leq m-1$），将 $c_t[i]$ 和 $c_t[j]$ 各减 $1$，同时将 $c_t[i-1]$ 和 $c_t[j+1]$ 各加 $1$。该操作仅可用于非特殊数组，即当 $t \neq k$ 时；
• 操作 2：选择两个整数 $i$ 和 $j$（满足 $2 \leq i \lt j \leq m-2$），将 $c_t[i]$ 和 $c_t[j]$ 各减 $1$，同时将 $c_t[i-1]$ 和 $c_t[j+2]$ 各加 $1$。该操作仅可用于特殊数组，即当 $t = k$ 时。

注意：若某次操作会导致数组中任一元素变为负数，则 Eric 不得执行该操作。

接下来，Eric 执行如下步骤：

• 对每个非特殊数组 $c_i$（即 $i \neq k$），Eric 仅使用操作 1，且至少执行一次；
• 对特殊数组 $c_k$，Eric 仅使用操作 2，且至少执行一次。

最后，Eric 丢弃原始数组 $b$。

现给定数组 $c_1, c_2, \dots, c_n$，你的任务是找出特殊数组，即确定 $k$ 的值；同时，还需确定在该特殊数组 $c_k$ 上执行操作 2 的次数。

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.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 10^5$，$7 \leq m \leq 3 \cdot 10^5$）—— 分别表示提供给你的数组个数，以及每个数组的长度。

接下来的 $n$ 行，每行包含 $m$ 个整数：$c_{i,1}, c_{i,2}, \dots , c_{i,m}$。

保证被丢弃的数组 $b$ 的每个元素均在区间 $[0,10^6]$ 内，因此对所有可能的 $(i,j)$ 对均有 $0 \leq c_{i,j} \leq 3 \cdot 10^{11}$。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

保证输入是严格按照上述过程生成的。

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.

对于每个测试用例，输出一行，包含两个整数——特殊数组的下标，以及对该特殊数组执行操作 2 的次数。在本题给定的约束条件下，可以证明该数值是唯一的，且不会超过 $10^{18}$，因此你可以使用 64 位整数来表示它。同时也可以证明，特殊数组的下标是唯一确定的。

本题中禁止进行 Hack。

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.

在第一个测试用例中，秘密数组 $b$ 为 $[0, 1, 1, 1, 1, 1, 1, 1, 0]$。数组 $c_1$ 和数组 $c_2$ 是通过使用操作 1 生成的；数组 $c_3$ 是通过使用操作 2 生成的。

对于数组 $c_1$，可选择 $i=4$ 和 $j=5$，执行一次操作 1 来生成它；对于数组 $c_2$，可选择 $i=6$ 和 $j=7$，执行一次操作 1 来生成它；对于数组 $c_3$，可选择 $i=4$ 和 $j=5$，执行一次操作 2 来生成它。

在第二个测试用例中，秘密数组 $b$ 为 $[20, 20, 20, 20, 20, 20, 20]$。同样可以发现，数组 $c_1$ 和数组 $c_2$ 是通过使用操作 1 生成的，而数组 $c_3$ 是通过使用操作 2 生成的。

在第三个测试用例中，秘密数组 $b$ 为 $[20, 20, 20, 20, 20, 20, 20, 20, 20]$。同样可以发现，数组 $c_1$ 和数组 $c_2$ 是通过使用操作 1 生成的，而数组 $c_3$ 是通过使用操作 2 生成的。