Grade Correction Ranking

In many universities, the GPA (Grade Point Average) is used to evaluate academic performance. Traditionally, students are ranked by their average scores. However, this method has drawbacks because the difficulty level of different courses (and the strictness of different professors) can significantly influence the average score. Consequently, students may be encouraged to choose easier courses to boost their average.

To overcome this issue, a correction scheme is applied. For each course \(i\), every student \(j\) who took that course has their grade \(G_{ij}\) adjusted by a correction value \(d_i\), so that the modified grade is \(G'_{ij} = G_{ij} + d_i\). The correction \(d_i\) is determined such that the adjusted average for course \(i\) equals the overall average of all courses taken by the students who selected course \(i\). Formally, let \(S_i\) be the set of students who took course \(i\) and let \(\text{Avg}_j\) denote the overall average score of student \(j\). Then the condition is: \[ \frac{\sum_{j \in S_i} (G_{ij} + d_i)}{|S_i|} = \frac{\sum_{j \in S_i} \text{Avg}_j}{|S_i|} \] which implies \[ d_i = \frac{\sum_{j \in S_i} \text{Avg}_j - \sum_{j \in S_i} G_{ij}}{|S_i|}. \]

After the adjustment, each student's final score is computed as the average of their adjusted grades. The ranking is then determined by sorting all students in descending order of their adjusted average scores. In case of ties, the student with the lower ID (1-indexed) is ranked higher.

inputFormat

The first line contains an integer \(n\) representing the number of students.

Each of the following \(n\) lines represents one student's record. Each record begins with an integer \(t\) (the number of courses the student took), followed by \(t\) pairs. Each pair consists of an integer \(c\) (the course id) and a number \(G_{ij}\) (the grade for that course). It is guaranteed that every student has taken at least one course. Course ids are positive integers.

outputFormat

Output a single line containing \(n\) integers separated by spaces. These integers are the 1-indexed student IDs sorted in descending order of their adjusted average scores. If two students have the same adjusted average score, the student with the smaller ID appears first.

sample

3
2 1 80 2 90
1 1 100
2 2 70 3 85

2 1 3