Who Owns the Prize?

Interview

Time limit4sMemory limit1024 MB

Summary

For each of four subjects in order, pick the highest-scoring student who has not yet won a prize, breaking ties by smaller student number.

Level: Medium4 of 10
Topics: Sorting, Implementation, Greedy, Array
Solved: No attempts yet

Problem

Hyemin's class has $N$ students, and each student is assigned a distinct number. This exam covers four subjects: Korean, English, Math, and Science. To encourage the students to study hard, the class decided to give a prize to the top scorer in each subject. The prizes are awarded in the order Korean, English, Math, Science, and since the class wants as many students as possible to receive a prize, each student can receive a prize only once. For example, if the student who places first in Korean also places first in Math, that student already received a prize for Korean and cannot receive another prize in a different subject. So for Math, the prize goes to the student with the highest score among those who have not yet received a prize. If there is a tie, the student with the smaller number receives the prize. Output the number of the student who receives the prize in each subject.

Input

The first line gives the number of students $N$ ( $4 \leq N \leq 200\,000$ ).

The next $N$ lines, from the second line to the $(N+1)$ -th line, each give a student's number $X$ ( $1 \leq X \leq N$ ) followed by their Korean score $A$ , English score $B$ , Math score $C$ , and Science score $D$ , in that order, as space-separated integers. Student numbers are distinct. ( $0 \leq A, B, C, D \leq 100$ )

Output

Print the numbers of the students who receive prizes, in the order Korean, English, Math, Science, separated by spaces.

Examples2

Example 1

Input

4
1 49 81 74 66
2 88 70 91 38
3 94 80 85 79
4 91 27 44 60

Expected output

3 1 2 4

Example 2

Input

8
3 65 21 8 61
8 69 2 19 58
7 85 40 42 29
4 45 1 58 56
2 4 37 83 33
6 75 60 12 42
5 80 20 74 49
1 8 26 93 33

Expected output

7 6 1 3