Background

Mirko’s village is going to hold an exam.

Problem Description

The exam is coming soon, and the students are stepping up their revision. Each student has two ability coefficients $A$ and $B$.

We say that one student will ask another student for help if and only if the other student’s $A$ and $B$ are both not less than this student’s.

Now you are given $n$ commands. There are two types:

• D A B: A new student arrives, with ability coefficients $A$ and $B$.

• P i: The $i$-th student wants to know whom to ask for help. To avoid wasting talent, if there are multiple possible students to ask, they will first choose the one with the smallest difference in coefficient $B$. If $B$ is the same, then they choose the one with the smallest difference in $A$.

The students are numbered in the order they arrive, starting from $1$.

Input Format

The first line contains an integer $n$, representing the total number of commands.

The next $n$ lines each contain one command. The exact format is as described above.

It is guaranteed that there do not exist two students with both coefficients identical.

Output Format

For each P i, output one integer: the index of the student that the $i$-th student wants to ask for help. If this student has nobody to ask, output NE.

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

NE
NE
NE

6
D 8 8
D 2 4
D 5 6
P 2
D 6 2
P 4

3
1

7
D 5 2
D 5 3
P 1
D 7 1
D 8 7
P 3
P 2

2
4
4

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$, $1 \le A, B \le 2 \times 10^9$.

Notes

This problem is translated from COCI2006-2007 CONTEST #4 T6 ISPITI.

Translated by ChatGPT 5