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

hide comments
Lars Krapf: 2023-02-24 22:16:01

WARNING: As dawid_zwiewka already mentioned below, the problem description is *wrong*. You have to print the lexicographically smallest permutation that is *less or equal* than k.

manav0299: 2021-03-05 21:29:59

Normal Backtracking, just use pruning

Last edit: 2021-03-07 20:56:43
krishnanshu: 2020-04-13 14:44:14

this question is similar N queen.

pabloskimg: 2019-02-07 16:42:06

Make sure to include pruning to avoid TLE

Last edit: 2019-02-07 16:42:58
rockintosh: 2019-01-24 16:00:50

Can anyone tell me if bfs based approach could help here?

sonianand966: 2018-10-13 21:23:21

I tried studying recursion and backtracking but it never works for me.
How can I improvise?

learnerinblack: 2018-06-10 19:18:01

Nothing to do with backtracking. In fact backtracking gives TLE.

Last edit: 2018-06-10 21:08:39
recurze: 2018-01-04 17:01:23

@ztoa1: I finally got what you meant! thank you :)

Arkadiusz Bulski: 2017-12-28 22:55:54

The formula seems to have buggy "+" placement, its a simple sum linear combination, right?

Last edit: 2017-12-28 22:56:11
dawid_zwiewka: 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

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