Ispiti

Mirko네 마을은 시험 기간이다. 모두가 최대한 적은 노력으로 시험에 통과하고 싶어 하지만, 쉬운 일이 아니다. Mirko는 자기보다 많이 아는 사람을 찾아 배우는 것이 최선이라는 것을 깨달았다. 모두가 그를 따라 했고, 이제 모두가 배울 사람을 찾고 있다.

학생이 시험에 얼마나 잘 준비되어 있는지는 두 정수 \(A\)와 \(B\)로 모델링할 수 있다. 수 \(A\)는 학생이 과목을 얼마나 잘 이해하는지를 나타내고, 수 \(B\)는 지식의 양에 비례한다.

마을의 우두머리인 Mirko는, 어떤 학생이 다른 학생에게 도움을 청하는 것은 그 학생의 두 수가 모두 자신의 수 이상일 때만 가능하다고 정했다(자신만큼 과목을 이해하지 못하거나 아는 것이 더 적은 사람에게는 아무도 묻지 않는다).

또한 학생들은 지식의 양의 차이를 최소화하려고 한다(훨씬 뛰어난 학생을 귀찮게 하지 않기 위해서다). 이 선택이 유일하지 않으면 이해도의 차이를 최소화하려고 한다.

Mirko네 마을은 최근 매우 인기 있는 동네가 되어, (시험 기간에 맞춰) 새 학생들이 계속 이사 온다. Mirko의 엄격한 규칙에 새 학생들은 혼란스러워하며 누구에게 가야 할지 모른다. 그들은 이웃 마을의 프로그래머에게 도움을 청하기로 했다.

입력의 첫째 줄에 마을에서 일어나는 질의와 전입의 횟수인 정수 \(M\) (\(1 \le M \le 100000\))이 주어진다. 다음 \(M\)개의 줄에는 다음 중 하나가 주어진다:

D A B, 이해도가 \(A\)이고 지식이 \(B\)인 학생이 이사 왔다

P i, \(i\)번째로 이사 온 학생이 누구에게 도움을 청해야 하는지 알고 싶어 한다

수 \(A\)와 \(B\)는 \(1\) 이상 \(1000000000\) 이하이다. 두 수가 모두 같은 두 학생은 없다.

각 질의(P i 줄)에 대해, \(i\)번째 학생이 누구에게 도움을 청해야 하는지 출력한다. 학생들은 마을에 이사 온 순서대로 (\(1\)부터) 번호가 붙는다. 도움을 받을 수 없는 학생이면 NE를 출력한다.

riseoj 작성

출처 COCI 2006/2007 Contest 4