BTCK - A problem of Backtracking

You have to solve the following problem with backtracking. You're given a sequence of 10 positive integers n1, n2, n3 ... n9, n10 and a positive value K.

To solve this problem you need to print a permutation a1, a2, a3 ... a10 of the numbers {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} such that a1 * n1 + a2 * n2 + a3 * n3 + ... + a10 * n10 ≤ K.

Input

In the first line, a single integer T, the number of test cases.

For each test case there will be two lines:

In the first line, 10 positive integers (1 ≤ n_i ≤ 10^9) separated by spaces.

In the second line, a single positive integer K (1 ≤ K ≤ 10^9).

Output

For each test case, print a line with the answer for that test case as following:

Among all the permutations that solve the problem according to the description above, print the lexicographically smallest.

You've to print the permutation in a single line, separating each integer by a simple space.

If no such permutation exists, print a single line with "-1".

Example

Input:
2
1 2 3 4 5 6 7 8 9 10
200
1 2 3 4 5 6 7 8 9 10
100

Output:
2 6 8 9 7 5 4 3 1 0
-1

Added by:BerSub
Date:2016-10-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2017-10-15 13:36:58
TIP: I got WA because I checked if permution is equal instead of equal OR LESS :)

Last edit: 2017-10-15 13:38:21
2017-06-19 21:36:58
@ d_y1997: Try stack data structure..!!
2017-06-02 00:25:40
can any one help me please , I am unable to find a recursive code for finding pemutations
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.