P6325 [COCI 2006/2007 #4] ISPITI

Mirko’s village is going to hold an exam.

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$.

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.

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`.

#### 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](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #4](https://hsin.hr/coci/archive/2006_2007/contest4_tasks.pdf) *T6 ISPITI*.** Translated by ChatGPT 5