CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)

前缀和之和之我是煞笔

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 bb of length mm, then he generates nn additional arrays c1,c2,…,cnc1,c2,…,cn, each of length mm, from the array bb, by the following way:

Initially, ci=bci=b for every 1≤i≤n1≤i≤n. Eric secretly chooses an integer kk (1≤k≤n)(1≤k≤n) and chooses ckck to be the special array.

There are two operations that Eric can perform on an array ctct:

• Operation 1: Choose two integers ii and jj (2≤i
• Operation 2: Choose two integers ii and jj (2≤iNote that Eric can't perform an operation if any element of the array will become less than 00 after that operation.

Now, Eric does the following:

• For every non-special array cici (i≠ki≠k), Eric uses only operation 1 on it at least once.
• For the special array ckck, Eric uses only operation 2 on it at least once.

Lastly, Eric discards the array bb.

For given arrays c1,c2,…,cnc1,c2,…,cn, your task is to find out the special array, i.e. the value kk. Also, you need to find the number of times of operation 22 was used on it.

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases. Description of test cases follows.

The first line of each test case contains two integers nn and mm (3≤n≤1053≤n≤105, 7≤m≤3⋅1057≤m≤3⋅105) — the number of arrays given to you, and the length of each array.

The next nn lines contains mm integers each, ci,1,ci,2,…,ci,mci,1,ci,2,…,ci,m.

It is guaranteed that each element of the discarded array bb is in the range [0,106][0,106], and therefore 0≤ci,j≤3⋅10110≤ci,j≤3⋅1011 for all possible pairs of (i,j)(i,j).

It is guaranteed that the sum of n⋅mn⋅m over all test cases does not exceed 106106.

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 10181018, so you can represent it as a 6464-bit integer. It can also be shown that the index of the special array is uniquely determined.

In this problem, hacks are disabled.

Example

input

Copy

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

output

Copy

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

Note

In the first test case, the secret array bb is [0,1,1,1,1,1,1,1,0][0,1,1,1,1,1,1,1,0]. Array c1c1 and array c2c2 are generated by using operation 1. Array c3c3 is generated by using operation 2.

For Array c1c1,you can choose i=4i=4 and j=5j=5 perform Operation 1 one time to generate it. For Array c2c2, you can choose i=6i=6 and j=7j=7 perform Operation 1 one time to generate it. For Array c3c3,you can choose i=4i=4 and j=5j=5 perform Operation 2 one time to generate it.

In the second test case, the secret array bb is [20,20,20,20,20,20,20][20,20,20,20,20,20,20]. You can also find that array c1c1 and array c2c2 are generated by using Operation 1. Array c3c3 is generated by using Operation 2.

In the third test case, the secret array bb is [20,20,20,20,20,20,20,20,20][20,20,20,20,20,20,20,20,20]. You can also find that array c1c1 and array c2c2 are generated by using Operation 1. Array c3c3 is generated by using Operation 2.

#include
using namespace std;
typedef long long ll;
typedef double db;
const int N=3e5+10;
ll sums[N],sum[N],n,m,t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            sums[i]=0;
            sum[i]=0;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                ll x;
                cin>>x;
                sum[j]=x+sum[j-1];
                sums[i]+=sum[j];
            }
        }
        int k=1;
        if(sums[n]!=sums[1]&&sums[n]!=sums[2])k=n;
        for(int i=2;i<=n-1;i++)
        {
            if(sums[i]!=sums[1]&&sums[i]!=sums[n])k=i;
        }
        cout<" "<<max(sums[1],sums[2])-sums[k]<<"\n";
 
    }
 
 
 
    return 0;
}