문제
최근 진우가 다니는 명문 고등학교에서는 높은 진학률로 유명하다. 이번 새 학기에 들어서면서 명문 고등학교는 새로이 신입생을 받고자 한다. 또한 명문 고등학교는 특이한 입시 전형으로도 유명한데 한 번에 신입생을 뽑는 것이 아니고, 수시로(아무때나) 지원을 받은 다음 시험을 봐서 입학을 하게 된다.
당신은 명문 고등학교의 이번에 새로이 들어오게 된 교직원이다. 당신은 우선 입학한 학생을 등록하고, 입학한 신입생 들이 학업에 어려움을 느껴서 도움을 청했을 때, 신입생을 도와줄 또 다른 신입생을 찾아주는 시스템을 관리하게 되었다.
신입생이 입학 했을 때는, 입학시험 때 평가 받은 수학 레벨과 영어 레벨을 저장하고, 입학 순서대로 학생에게 번호를 부여 해주게 된다(1번부터 시작).
그리고 신입생이 도움을 요청했을 때는 해당 신입생 보다 수학과 영어의 레벨이 높거나 같은 학생을 찾아야 한다. 만약 그러한 학생들이 여러 명이 있을 경우 도움을 청한 학생과 수학의 레벨의 차이의 합이 가장 적게 나는 학생을 찾아줘야 하며, 이마저 같은 사람이 있을 경우 영어 레벨의 차이가 적은 학생을 찾아줘야 한다(신입생이 신입생을 도와주는 것은 명문 고등학교의 전통이며, 상급생이 신입생을 도와주는 것은 엄격하게 금지되어있다).
처음에는 이러한 시스템을 눈으로 보면서 해왔지만 점점 신입생이 늘어나면서 더 이상 눈과 손으로는 하기 힘들어지게 되었다. 진우를 위해 이 시스템의 프로그램을 작성해주자.
입력
입력의 첫 번째 줄에는 입력되는 개수 N(1≤N≤200,000)이 입력된다.
다음 N개의 줄에는 2가지 입력이 들어올 수 있다.
● D A B : 영어 레벨이 A고 수학 레벨이 B인 학생이 입학했음을 알리는 명령.
● P i : i 번째 학생이 도움을 청할 때, 도움을 줄 수 있는 학생을 찾는 명령.
A와 B는 1이상 2x109 이하의 정수이며, A와 B가 같은 경우는 존재하지 않는다.
출력
P가 입력되었을 때 i번째 학생을 도와주는 학생의 번호를 출력한다.
학생의 번호는 입학한 순서대로 매겨진다(1부터 시작).
만약 도와줄 수 있는 학생이 없을 경우 “NE”를 출력한다.
예제 #1
6
D 3 1
D 2 2
D 1 3
P 1
P 2
P 3
NE
NE
NE
예제 #2
6
D 8 8
D 2 4
D 5 6
P 2
D 6 2
P 4
3
1
예제 #3
7
D 5 2
D 5 3
P 1
D 7 1
D 8 7
P 3
P 2
2
4
4
로그인해야 코드를 작성할 수 있어요.