beecrowd | 1303

Spurs Rocks

IX Maratona de Programação IME-USP, 2005 Brazil

Timelimit: 1

The San Antonio is the city team in the NBA. It has been the champion of its conference several times and revealed several excellent players.


In a basketball championship all the teams play each other in a single round. A win is worth two points and a defeat is worth one point (there are no draws in basketball). In case of ties the team with the best "average basket" gets the lead. The "average basket"is given by the ratio between the number of points scored by the team divided by the number of points received (in the unlikely event of a team winning all league games without losing any baskets, the basket average is given by the average number of points scored). If there is still a tie, the team that scored more points takes advantage. And if the ties persists, the team with the lowest number of entried in the league gets a better position.


Your task in this problem is to make a program that receives the results of the games of the championship and prints the final rank.

Input

There are several test cases. For each instance is given the number 0 ≤ n ≤ 100 of teams in the league. The value n = 0 indicates the end of dataset. Next there are n (n-1) / 2 lines indicating the results of the matches. In each one of these lines there are four integers x, y, z and w. The integers x and z belong to the interval {1, 2,. . . , n} and represent the registration numbers of the teams in the league. The integers y and w are the number of points the team x and z score in the match described.

Output

For each test case solved, you should print the message "Instancia h" where h is an integer, and increasing sequentially from 1. On the next line you should print a permutation of the integers from 1 to n representing the championship rank.

A blank space should be printed between each one of these integers and a blank line must be printed between two outputs (test cases).

Sample Input Sample Output

5
1 102 2 62
1 128 3 127
1 144 4 80
1 102 5 101
2 62 3 61
2 100 4 80
2 88 5 82
3 79 4 90
3 87 5 100
4 110 5 99
0

Instancia 1
1 2 4 5 3