#894 KMO

Statement

Statement language

You are given a sequence $a=(a_1,a_2,\cdots,a_N)$ of length $N$ and an integer $K$ .

A sequence $b=(b_1,b_2,\cdots,b_N)$ of length is called if it satisfies both conditions below.

Find a good sequence that minimizes $\displaystyle\sum_{i=1}^{N}a_i b_i$ .

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print an optimal good sequence $b_1,b_2,\cdots,b_N$ on one line, separated by spaces.

#	Score	Constraints
1	20	$N\leq8$ . The sum of $N$ in one input file is at most $1000$ .
2	25	$K=2$ .

Sample 1

Input

Output

0
2 2 1 1
2 2 1

The minimum costs of the three test cases are $0$ , $13$ , and $5$ , respectively.

Sample 2

Input

1
8 3
1 1 2 3 5 8 13 21

Output

4 4 3 3 2 2 1 1

The output is one possible optimal sequence.