Travelling around the world is really tiring, especially for Mr. Ed and his pals, who carry heavy luggage. In order to reduce the fatigue, they planned to share the weight of everyone’s luggage between their friends. Let’s say that person i was carrying wi kilograms of luggage and this person has fi friends in the group, then he distributed equitably that weight such that every friend received exactly wi/fi kilograms from him. Nobody distributed luggage they had just received. At the first day of a trip, they distributed the luggage everyone brought from home; by the second day they distributed the luggage received on day one distribution; by the third day of the trip, received luggage from day two is shared; and so on. They kept doing this while they were travelling. When Mr. Ed arrived home from his latest trip to the World Finals, he noticed that the group forgot to return everyone’s luggage! He remembers that there was n people (numbered from 1 to n) travelling in the group, the trip lasted k days and everyone brought a real non-negative number of kilograms at the beginning of the trip. After calling everyone by phone, Mr. Ed wrote down the list of everybody’s friends and how many kilograms of luggage they ended up with, including his. Mr. Ed is exhausted from the trip, so he asked you to find how many luggage each one initially brought. Input The input will contain several test cases. The first line of every test case will contain 3 integers n, m and k: the number of people in the group, the number of friendship relations and the number of days the trip lasted (2 ≤ n ≤ 16, n ≤ m ≤ n × (n−1) and 1 ≤ k ≤ 64). Each of the next n lines contains a single real number 0 ≤ wi ≤ 1600 (with up to 200 digits to the right of the decimal point): the kilograms of luggage the i-th person ended up with. The next m lines contain 2 integers a and b (1 ≤ a, b ≤ n and a ̸= b), each line describing a friendship relation such that person a considers person b a friend. Notice that relations may not be mutual. There will not be repeated relations and every person will consider at least one friend. The last test case is followed by a single line containing 3 zeroes. Output For each test case print n numbers; the i-th number represents the kilograms of luggage person i brought initially to the trip, rounded (half up) to the nearest integer value. You can safely assume that there is at least one solution for each test case, but if there are multiple solutions you must print ‘Lost luggage!’ See example below for details about output format. Note: First test case is pretty straightforward; both people in the group are mutual friends and they alternated their luggage for 7 days, ending up with 1 kg of luggage each. For the second test: initially person 1 brought 3 kg of luggage, person 2 brought 1 kg and person 3 brought 2 kg. Person 1 considers person 2 a friend, while person 2 considers person 3 a friend and this last one considers person 1 a friend. After one day of the trip, person 1 gives his initial 3 kg to person 2, this one gives 1 kg of luggage to person 3 and similarly he gives 2 kg to person 1. By the second day, person 1 gives the 2 kg he received in the previous day to person 2, this one gives last day 3 kg to person 3 and finally person 3 passed his 1 kg of luggage to person number 1. This is the only way person 1, 2 and 3 could end up with 1, 2 and 3 kilograms respectively. There are multiple ways third case result could be achieved, one of them being: person 1 brought 2 kg of luggage, person 2 brought 3 kg and person 3 didn’t bring any luggage to the trip.
2/2 Sample Input 227 1.00 1.00 12 21 332 1.00 2.00 3.00 12 23 31 341 1.50 2.00 1.50 12 21 23 32 000 Sample Output Case #1: 1 1 Case #2: 3 1 2 Case #3: Lost luggage!