스터디장 홍준

홍준이는 동아리의 스터디장을 맡고 있다. 이 스터디에 오는 학생들의 주된 목적은 다 같이 모여 공부하는 것이 아니라, 모르는 내용을 질문하는 것이다. 홍준이도 이 점을 잘 알고 있다.

각 학생의 능력은 두 자연수 A와 B로 표현한다. A는 학생이 이 과목을 얼마나 잘 이해하고 있는지를 나타내고, B는 이 과목에 대한 지식의 깊이를 나타낸다. 값이 클수록 이해도가 높고 지식이 깊다는 뜻이다.

어떤 학생은 자신보다 이해도가 낮거나 지식의 깊이가 낮은 학생에게는 질문하지 않는다. 지식의 깊이가 같다면 자신보다 이해도가 높은 학생에게는 질문할 수 있다. 질문할 수 있는 학생 중에서는 지식의 깊이 차이가 가장 작은 학생을 원하고, 그런 학생이 여러 명이면 이해도 차이가 가장 작은 학생을 원한다.

홍준이는 학생들의 성향을 잘 파악하고 있어서, 종종 학생들에게 누구에게 질문하면 좋을지 묻는 질문을 받는다. 홍준이를 도와 각 질문에 답하는 프로그램을 작성하시오.

시간이 지남에 따라 동아리에 학생이 새로 가입한다. 동아리를 탈퇴하는 학생은 없다.

첫 줄에 상황의 수 N이 주어진다. (1 <= N <= 200000)

다음 N개의 줄에는 아래 두 종류의 상황 중 하나가 주어진다.

• D A B: 이해도가 A이고 지식의 깊이가 B인 학생이 동아리에 가입한다.
• P i: i번째로 가입한 학생이 누구에게 질문해야 하는지 묻는다.

주어지는 A와 B는 1 이상 2 x 10^9 이하이다. A와 B가 모두 같은 학생은 존재하지 않는다.

각 P i 상황마다 답을 한 줄에 출력한다. 질문할 수 있는 학생이 존재하지 않으면 NE를 출력한다. i번째로 가입한 학생이 k번째로 가입한 학생에게 질문해야 한다면 k를 출력한다.