MINUS - Minus Operation

no tags 

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 pi, which denotes that you are to wipe the pi-th and (pi+1)-th number in the current sequence and use their substraction 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

hide comments
singhsauravsk: 2017-04-16 07:10:11

Awesom problem to get concept cleared in Dynamic Programming.

Last edit: 2017-06-04 23:58:13
ashish22_dwd: 2016-09-12 21:18:47

Nice problem.. learnt a lot

Pagan Min: 2015-05-24 15:05:22

nice question on knapsack...worth solving

rafael859: 2014-09-29 21:48:53

Don't forget the blank line! It caused me way too many WAs! (Or problemsetter could try to write a better judge...)

maniAC: 2014-09-04 20:46:50

Nice problem.

­: 2014-07-17 11:14:36

in 2 numbers chosen is the subtraction always have to be a[i-1]-a[i]?

Suriya Narayanan: 2014-06-29 15:14:52

easy DP.. solved \m/

:D: 2012-06-19 06:18:38

Series of operations you perform and resulting sequences:

12 [10 4] 3 5

10-4 = 6
12 6 [3 5]

3-5 = -2
12 [6 -2]

6 - -2 = 8
[12 8]

12 - 8 = 4
4

conio: 2012-06-18 09:28:51

i cant understand problem itself..can anyone expalin plz..


Added by:Fudan University Problem Setters
Date:2007-11-03
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C99 ERL JS-RHINO OBJC SQLITE
Resource:description by Blue Mary; standard program and test data by Zhou Yisu