JARJAR - Helping Jar Jar Binks

A job has been assigned to Jar Jar Binks, it goes as follows:

There are N spaceships parts, each with a weight of Wi kg. Given a weight W, he has to show how many parts can be used in order to make a ship with a weight of exactly W kg. He has to show all possible solutions, of course if possible.

Everybody knows Jar Jar Binks particularly because of his clumsiness, so you have to help him. Write a program that solves his problem!

Input

There will be several cases, each beginning with two integers N, Q (1 ≤ N ≤ 60, 0 ≤ Q ≤ 10000).

Next there will be N positive integers representing the weights of the N spaceship parts (1 ≤ Wi ≤ 1000).

Q lines will follow, each one with only one (not necessarily positive) integer W, the total weight of the spaceship.

End of input will be denoted with N = 0 and Q = 0. This case should not be processed.

Output

Print a line with K integers per query in ascending order. They must represent the amount of pieces that can be used to make a spaceship with weight W.

If there is no way to make a spaceship with weight W, output a line with the string “That's impossible!” (quotes to clarify)

Example

Input:
5 4
1 2 3 1 1
3
5
1
9
0 0

Output:
1 2 3
2 3 4
1
That's impossible!

Explanation of the query W = 5

A spaceship with weight = 5 kg can be formed with 2, 3 and 4 parts, for example:

  • 2 kg + 3 kg = 5 kg
  • 3 kg + 1 kg + 1 kg = 5 kg
  • 1 kg + 1 kg + 1 kg + 2 kg = 5 kg

Added by:Samuel Nacache
Date:2015-05-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY

hide comments
2018-05-17 03:33:44
notice that "0" is impossible!
2016-07-31 10:31:16
Good combination of dp and bitmask!
2016-05-29 21:37:20 SUBHAM SANGHAI
Note W can be less than or equal to 0 ,for which ans will be "That's impossible!"
2015-12-19 07:37:30 Jacob Plachta
Excepted answer for W=0 is "impossible", not "0"
2015-10-10 23:41:07 Alex Anderson
What's the point of having a query with "negative weight" ?
Make Binks have a bad day

Last edit: 2015-11-04 23:49:03
2015-07-25 19:42:16 Scape
A very nice problem.
2015-06-15 20:55:55 sdda
after making changes in my code @Samuel, now its showing WA after the sixth case.........is there anything i am missing......
2015-06-12 15:51:00 Samuel Nacache
@sdda @goyal both are getting WA on test case 0 (not the same as the input)!
2015-06-07 12:39:07 sdda
Same, i m also gettin wrong ans aftr 9 th case Bt y :/
2015-06-01 17:32:35 goyal
getting wa after 9th test case
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.