Magical Array

题意翻译

给定一个数组 $b$，长度为 $n$。 现选定 $k$ 并构建数组 $c_1,c_2,\dots,c_m$，并且长度均为 $n$。 起初，对于任意的 $i\in[1,m]$ 和 $j\in[1,n]$ 有 $c_{i_j}=b_j$。 现有两种操作。 > 选定 $i,j$ 使得 $1< i< j< n$。将 $a_i$ 和 $a_j$ 自减，将 $a_{i-1}$ 和 $a_{j+1}$ 自增。 > 选定 $i,j$ 使得 $1< i< j< n-1$。将 $a_i$ 和 $a_j$ 自减，将 $a_{i-1}$ 和 $a_{j+2}$ 自增。 对 $c_k$ 执行 $x$ 次第二种操作。对其他的数组执行若干次（可能不同的次数）第一种操作。给出 $c_1,c_2,\dots,c_m$，求出 $k$ 和 $x$。

题目描述

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.

输入输出样例

输入样例 #1

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

输出样例 #1

3 1
3 10
3 15
3 20
3 25
3 30
1 1378716

说明

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$，长度为 $n$。 现选定 $k$ 并构建数组 $c_1,c_2,\dots,c_m$，并且长度均为 $n$。 起初，对于任意的 $i\in[1,m]$ 和 $j\in[1,n]$ 有 $c_{i_j}=b_j$。 现有两种操作。 > 选定 $i,j$ 使得 $1< i< j< n$。将 $a_i$ 和 $a_j$ 自减，将 $a_{i-1}$ 和 $a_{j+1}$ 自增。 > 选定 $i,j$ 使得 $1< i< j< n-1$。将 $a_i$ 和 $a_j$ 自减，将 $a_{i-1}$ 和 $a_{j+2}$ 自增。 对 $c_k$ 执行 $x$ 次第二种操作。对其他的数组执行若干次（可能不同的次数）第一种操作。给出 $c_1,c_2,\dots,c_m$，求出 $k$ 和 $x$。