시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 177 77 15 25.000%

문제

홍준이는 동아리에서 스터디장을 맡고 있다. 이 스터디에 오는 사람들의 주된 목표는 다 같이 모여서 공부를 하는 것이 아닌 모르는 것을 질문하는 것 이다. 홍준이도 이러한 점을 잘 알고 있다.

스터디에 있는 학생들의 능력을 두 개의 자연수 A와 B로 표현할 수 있다. A는 학생이 얼마나 잘 이해하고 있는지를 나타내고, B는 이 과목에 대한 학생의 지식의 깊이 정도를 나타낸다. 물론 값이 클 수록 이해를 더 잘하고, 지식의 깊이가 깊은 것을 의미한다.

스터디에 있는 학생은 자신 보다 이해를 못하거나, 지식의 깊이가 낮은 학생한테 질문하지 않는다. 하지만, 지식의 깊이가 같고, 자신보다 이해를 잘한 학생한테는 질문한다. 동시에 지식의 깊이 차이가 최소인 학생에게 질문하고 싶어한다. 만약 지식의 깊이 차이가 최소인 사람이 여러 명인 경우, 이해 정도의 차이가 최소인 사람한테 질문하고 싶어한다.

홍준이는 학생들의 이러한 성향을 매우 잘 파악하고 있고, 종종 학생들로부터 누구한테 질문하면 좋겠냐는 질문을 받는다. 홍준이를 도와 학생들의 질문에 대답해주는 프로그램을 작성하시오.

시간이 지남에 따라 동아리에 사람이 더 가입한다. 동아리를 탈퇴하는 사람은 없다.

입력

첫 줄에는 상황의 수 N이 주어진다. (1 ≤ N ≤ 200 000)

그 다음 N개의 줄에 다음과 같은 2가지 종류의 상황이 주어진다.

  • "D A B", 이해의 정도가 A이고, 지식의 깊이가 B인 학생이 동아리에 가입한다.
  • "P i", i번째로 가입한 학생이 누구한테 질문을 해야하는지 물어온다.

주어지는 수 A, B는 1이상, 2ㆍ10 9 이하다. 그리고 A, B가 동일한 학생은 존재하지 않는다.

출력

각 줄에 "P i"의 상황에 대한 답을 출력해야 한다. 만약 질문할 수 있는 학생이 존재하지 않는 경우 "NE"를 출력한다. 만약 i번째로 가입한 학생이 질문하는 학생이 k번째로 동아리에 가입했다면, 수 k를 출력한다.

예제 입력

6
D 3 1
D 2 2
D 1 3
P 1
P 2
P 3

예제 출력

NE
NE
NE

힌트