There are n integer numbers listed in one line. Every time you can arbitrarily choose two neighboring integers, kick them out and write down the result of the first number subtract the second number instead. Now, you want to get number m after you perform this operation n-1 times.

Input

Multiple test cases, the number of them is given in the very first line.

For each test case:

The first line contains two space-separated integers n (1 <= n <= 100) and m (-500 <= m <= 500). n lines follow, each contains a single integer (in the range [0,100]) denotes the original numbers.

Output

For each test case:

You should output n-1 lines, each contains a single integer p_i, which denotes that you are to wipe the p_i-th and (p_i+1)-th number in the current sequence and use their subtraction instead. Each line of your output should not have any leading or trailing white spaces.

You may assume that there is always a valid solution to each test case in the input file. If there are multiple solutions, any of them will be accepted.

Print a blank line after each test case.

Example

Input:
1
5 4
12
10
4
3
5

Output:
2
3
2
1