github.com/captn3m0/codechef.git

---
category_name: challenge
problem_code: INTCOMB
problem_name: 'Integer Combinations Of Vectors'
languages_supported:
    - C
    - CPP14
    - JAVA
    - PYTH
    - 'PYTH 3.5'
    - PYPY
    - CS2
    - 'PAS fpc'
    - 'PAS gpc'
    - RUBY
    - PHP
    - GO
    - NODEJS
    - HASK
    - rust
    - SCALA
    - swift
    - D
    - PERL
    - FORT
    - WSPC
    - ADA
    - CAML
    - ICK
    - BF
    - ASM
    - CLPS
    - PRLG
    - ICON
    - 'SCM qobi'
    - PIKE
    - ST
    - NICE
    - LUA
    - BASH
    - NEM
    - 'LISP sbcl'
    - 'LISP clisp'
    - 'SCM guile'
    - JS
    - ERL
    - kotlin
    - PERL6
    - TEXT
    - 'SCM chicken'
    - CLOJ
    - COB
    - FS
max_timelimit: '7.95992'
source_sizelimit: '50000'
problem_author: friggstad
problem_tester: anshuman_singh
date_added: 8-09-2010
tags:
    - challenge
    - friggstad
    - oct10
editorial_url: 'http://discuss.codechef.com/problems/INTCOMB'
time:
    view_start_date: 1286793691
    submit_start_date: 1286793691
    visible_start_date: 1286793691
    end_date: 1735669800
    current: 1525199664
is_direct_submittable: false
layout: problem
---
All submissions for this problem are available.You are given a collection of n integer-valued vectors **v**1, **v**2, ..., **v**n (i.e. integer arrays) of some fixed dimension. An integer combination of these vectors is a vector of the form **v** = c1**v**1 + ... + cn**v**n where each ci is an integer. Here, the j'th component **v**\[j\] is precisely c\[1\]**v**1\[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**1, ..., **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

<pre>
<b>Input:</b>
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

<b>Output:</b>
-3 1
-1 0 1 0
</pre>### 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.