Study Leader Hongjun

Hongjun leads a study group in a club. The students who come to this study group mainly want to ask questions about what they do not know, rather than simply gather and study together. Hongjun understands this well.

Each student's ability is represented by two natural numbers, A and B. A is how well the student understands the subject, and B is the depth of the student's knowledge. Larger values mean better understanding and deeper knowledge.

A student does not ask a student whose understanding is lower than their own or whose knowledge depth is lower than their own. If the knowledge depth is the same, they may ask a student whose understanding is higher than their own. Among all students they can ask, they want the student with the smallest difference in knowledge depth. If there are several such students, they want the one with the smallest difference in understanding.

Hongjun is often asked which student would be best to ask. Write a program that helps Hongjun answer these questions.

As time passes, more students join the club. No student leaves.

The first line contains the number of events N. (1 <= N <= 200000)

Each of the next N lines contains one of the following two event types.

• D A B: a student whose understanding is A and whose knowledge depth is B joins the club.
• P i: the i-th student to join asks whom they should ask.

Each given A and B is at least 1 and at most 2 x 10^9. No two students have the same pair (A, B).

For each P i event, print one answer on its own line. If there is no student the queried student can ask, print NE. Otherwise, if the queried student should ask the k-th student to join the club, print k.