상품의 주인은?

면접 대비

시간 제한4초메모리 제한1024 MB

요약

네 과목을 차례로, 아직 상을 받지 않은 학생 중 점수가 가장 높은 학생에게 주고 동점이면 번호가 빠른 학생에게 준다.

난이도: 보통10점 중 5점
유형: 정렬, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

혜민이네 반은 총 $N$ 명의 학생으로 이루어져 있으며 학생마다 번호가 다르게 배정되어 있다. 이번 시험은 국어, 영어, 수학, 과학 총 4과목으로 진행되며, 학생들이 공부를 열심히 할 수 있게 과목별 1등에게 상품을 주기로 했다. 수상은 국어, 영어, 수학, 과학 순서로 하며 최대한 많은 학생에게 상품을 주고 싶기 때문에 학생마다 상품은 한 번만 받을 수 있다. 예를 들어 국어 과목에서 1등 한 사람이 수학 과목에서 또 1등을 한다면 국어 과목에서 상품을 받았기 때문에 이 학생은 다른 과목에서 상품을 더 받을 수 없다. 따라서 수학 과목은 상품을 받지 않은 학생 중에 점수가 가장 높은 학생이 상품을 받는다. 단, 동점이 있으면 번호가 빠른 사람이 상품을 받는다. 과목별 상 받을 사람의 번호를 출력하시오.

입력

첫 번째 줄에 학생의 수 $N$ ( $4 \leq N \leq 200\\,000$ )이 주어진다.

두 번째 줄부터 $N+1$ 번째 줄까지 $N$ 개의 줄에 걸쳐서 학생의 번호 $X$ ( $1 \leq X \leq N$ )와 학생의 국어 점수 $A$ , 영어 점수 $B$ , 수학 점수 $C$ , 과학 점수 $D$ 가 순서대로 공백을 기준으로 정수로 주어진다. 학생의 번호는 중복될 수 없다. ( $0 \leq A, B, C, D \leq 100$ )

출력

국어, 영어, 수학, 과학 순서대로 상품을 받는 학생의 번호를 공백으로 구분하여 출력한다.

예제2

예제 1

입력

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

예상 출력

3 1 2 4

예제 2

입력

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

예상 출력

7 6 1 3