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 < j \leq m-1$$$),从 $$$c_t[i]$$$ 和 $$$c_t[j]$$$ 中减去 $$$1$$$,并添加 $$$1$$$ $$$c_t[i-1]$$$ 和 $$$c_t[j+1]$$$。该操作只能用于非特殊数组,即 $$$t \neq k$$$ 时。;
- 操作 2:选择两个整数 $$$i$$$ 和 $$$j$$$ ($$$2 \leq i < j \leq m-2$$$),从 $$$c_t[i]$$$ 和 $$$c_t[j]$$$ 中减去 $$$1$$$,并添加 $$$1$$$ $$$c_t[i-1]$$$ 和 $$$c_t[j+2]$$$。该操作只能在特殊数组上使用,即当 $$$t = k$$$ 时。请注意,如果在该操作之后数组的任何元素将变得小于 $$$0$$$,Eric 将无法执行该操作。
现在,Eric 执行以下操作:
- 对于每个非特殊数组 $$$c_i$$$ ($$$i \neq k$$$),Eric 只对其使用至少一次操作 1。
- 对于特殊数组 $$$c_k$$$,Eric 只对其使用至少一次操作 2。
最后,Eric 丢弃了数组 $$$b$$$。
对于给定的数组 $$$c_1, c_2, \dots, c_n$$$,你的任务是找出特殊数组,即值 $$$k$$$。另外,您还需要找到对其使用$$$2$$$操作的次数。
输入
第一行包含一个整数 $$$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$$$。
保证输入是按照上述过程生成的。
输出
对于每个测试用例,输出一行包含两个整数 - 特殊数组的索引以及对其执行操作 2 的次数。可以看出,在问题给出的约束下,这个值是唯一的,不会超过$$$10^{18}$$$,所以你可以将它表示为$$$64$$$位整数。还可以看出,特殊数组的索引是唯一确定的。
在这个问题中,黑客被禁用。
示例
输入 #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
注意
在第一个测试用例中,秘密数组 $$$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生成的。