Luffy Wants a Bike

All submissions for this problem are available.
The Straw Hat Pirates are on Sabaody Archipelago. Luffy sees a bubble bike. As usual, he insists on buying one for himself but the shopkeeper is very stubborn and accepts only exact amount of money.
Nami gave Luffy only certain values of coins.
We all know that Luffy doesn’t like to study so he is weak in maths. You have to help him decide on the minimum number of coins he should use in order to pay for the bike. In case you cannot form the exact amount using the given coins give the output as 1.
Assume you have infinite supply of coins of the given value.
Input
The first line of the input contains a single integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two spaceseparated integers N and M, denoting the number of different values of coins he has and number of types of bike, respectively. The second line of each test case contains N space separated integers Vi’s denoting the value of coins Nami gave Luffy. The third line of each test case contains M space separated integers Pi’s denoting the price of different types of bike.
Output
For each test case output M space separated integers denoting the minimum number of coins needed to pay for that bike. In case it is not possible to form the exact price, output 1.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N ≤ 50
 1 ≤ M ≤ 500
 1 ≤ Vi ≤ 500
 1 ≤ Pi ≤ 10000
Example
Input:1
Output:
3 4
3 6 9
15 16 21 222 1 3 1
Explanation
Example case 1. Here, 15 can be made using 1 coin of value 6 and 1 value of coin 9. So, the solution is 2.
For 16, there are no such combinations of the given values, that add upto 16. So, the solution is 1.
Author:  manasvi2001 
Tags  manasvi2001 
Date Added:  16032013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 