Integer Combinations Of Vectors

All submissions for this problem are available.

You are given a collection of n integer-valued vectors v₁, v₂, ..., v_n (i.e. integer arrays) of some fixed dimension. An integer combination of these vectors is a vector of the form v = c₁v₁ + ... + c_nv_n where each c_i is an integer. Here, the j'th component v[j] is precisely c[1]v₁[j] + ... + c[n]v_n[j].

Define the length of a vector x = (x[1], x[2], ..., x[n]) to be the square root of x[1]*x[1] + x[2]*x[2] + ... + x[n]*x[n]. Your task is to find a short integer combination of vectors v₁, ..., v_n whose length is non-zero.

Input

The first line contains a single integer T ≤ 30 indicating the number of test cases to follow. Each test case begins with two integers n and d, both between 1 and 100, where n is the number of vectors in the test case and d is their common dimension.

Then n lines follow, each containing d integers. The j'th number on the i'th line is the j'th component of vector v_i (i.e. v_i[j]). Every such integer is between -100 and 100 (inclusive). None of the input vectors will be a zero vector. This means that for each i, at least one j is such that v_i[j] ≠ 0.

Test cases are separated by a single blank line including a blank line preceding the first test case.

Output

For each test case, you are to output a single line consisting of n integers where the i'th integer is the value of the coefficient c[i] in some integer combination of the input vectors. The value must satisfy -100 ≤ c[i] ≤ 100.

Furthermore, the integer combination of the input vectors using these coefficients must produce a non-zero vector. That is, the vector must have positive length.

Example

Input:
2

2 1
14
35

4 5
1 4 1 2 5
1 2 3 4 5
0 1 2 3 7
1 -2 3 -4 5

Output:
-3 1
-1 0 1 0

Scoring

The score for a test case is the length of the integer combination as given by the output coefficients divided by the length of the shortest input vector. The total score for the entire data set is simply the sum of the scores of the individual test cases.

Example

The integer combination represented by the output in the first test case is -3*(14) + 1*(35) = (-7). The length of the vector (-7) is simply 7. The length of the shortest vector in the input is 14 so the score for this case is 0.5.

The integer combination represented by the output for the second test case is -1*(1,4,1,2,5) + 1*(0,1,2,3,7) = (-1,-3,1,1,2). The length of this is the square root of 1*1 + 3*3 + 1*1 + 1*1 + 2*2 = 16, so the length is 4. The shortest vector in the input is the first one having length equal to the square root of 1*1 + 4*4 + 1*1 + 2*2 + 5*5 = 47 which is roughly 6.855. Thus, the score for the second case is 4/6.855 = 0.5835.

Input Distribution

Some of the test data is randomly generated by simply selecting values for the components of the vectors uniformly at random in the range -100 to 100 and keeping the vector if it is non-zero.

Other test data is generated by generating n-1 of the vectors as above, computing a random integer combination of these vectors and then creating the final vector so that subtracting it from the random integer combination results in a very short vector. This final vector may be any of the n vectors in the input.