Welcome to ZOJ
77 - The 9th Zhejiang University Programming Contest - E
Beverages for Sale

Time Limit: 2 Seconds      Memory Limit: 32768 KB      Special Judge

What a hot summer holiday! Tom has got several delicious beverages and he wants to sell them to his friends. Tom is so greedy that he wants to get all money of his friends and he also wants to sell all his beverages out, so he must decide the prices of each beverage carefully. Tom knows that for each of his friends:

1. the amount of money he/she has now;
2. his/her favorite set of beverages (They would only accept beverages in their own favorite sets); and
3. he/she is so tightfisted that only the cheapest beverages in his/her favorite set will be purchased, and he/she wants to buy as many as he/she can pay.(If there are more than one cheapest in the set, he/she may purchase partial beverage from any of them and ignore the taste differences.)

Since you're an ace programmer, Tom wants you to help him to sell all his beverages out and get all the money his friends have.


There are multiple test cases. The first line of input contains an integer T (T<=50) indicating the number of test cases. Then T test cases follow.

Each case starts with two integers N and M, which are the number of kinds of beverages and the number of Tom's friends, respectively (1 <= N, M <= 30). Then M + 2 lines follow. The first line contains N positive integers (less than 60000) separated by one space, indicating the amount of each beverage. Notice that although the amount of beverage is integer, the beverage is dividable. Thus any amount that does not exceed the given amount can be sold. The second line contains M positive integers (less than 60000) separated by one space, indicating that the amount of money each Tom's friend has. The money is also dividable. Each of the next M lines each starts with a positive integer K and then K integers chosen from 1 to N, which are the indices of beverages, indicating the favorite set of each Tom's friend.


For each test case, output the unit prices of all the kinds of beverage in a line. Each number is separated buy a space. If Tom cannot get all his friends' money output "Impossible" instead. Do not worry about the precision of the answer since answers with error within 10-4 will be accepted.

Sample Input

2 2
1 1
1 1
1 1
1 1
2 2
1 1
1 1
1 2
1 1

Sample Output

1.0 1.0

Test case 1: No one likes the beverage 2 so Tom cannot sell all beverages.
Test case 2: Sell beverage 1 to Tom's second friend and beverage 2 to his first friend with price 1 is a solution.

Author: CAO, Peng
Contest: The 9th Zhejiang University Programming Contest
Submit    Status