77 - The 9th Zhejiang University Programming Contest - E
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;
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.
2 2 2 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 2 1 1
Impossible 1.0 1.0
Author: CAO, Peng
Contest: The 9th Zhejiang University Programming Contest