[COCI2006-2007#4] ISPITI
题目背景
Mirko 的村子要进行一场考试。
题目描述
考试在即,学生们赶快加紧了复习的进度。每个学生都有两个能力系数 $A\ B$。
我们认为一个学生会向另一个学生求助,当且仅当另一个学生的 $A$ 和 $B$ 都不小于这个学生。
现在给出 $n$ 条指令,有以下两种类型:
- `D A B` 来了一个学生,他的两个能力系数为 $A$ 和 $B$。
- `P i` 第 $i$ 个学生想知道找谁帮忙。为了不大材小用,如果有多人可以求助,他会首先选择系数 $B$ 相差最小的。如果 $B$ 相同,则首选 $A$ 相差最小的。
其中学生的编号由入场的顺序从 $1$ 开始依次编排。
输入输出格式
输入格式
输入第一行为一个整数 $n$ ,表示指令的总数。
接下来的 $n$ 行,每行一个指令,具体格式参照题目描述。
保证不会存在任意两个学生的两个指数都相同。
输出格式
对于每一个 `P i`,输出一个整数,为第 $i$ 个学生想向哪个编号的学生求助。如果这个学生没有可以求助的对象,则输出 `NE`。
输入输出样例
输入样例 #1
6
D 3 1
D 2 2
D 1 3
P 1
P 2
P 3
输出样例 #1
NE
NE
NE
输入样例 #2
6
D 8 8
D 2 4
D 5 6
P 2
D 6 2
P 4
输出样例 #2
3
1
输入样例 #3
7
D 5 2
D 5 3
P 1
D 7 1
D 8 7
P 3
P 2
输出样例 #3
2
4
4
说明
#### 数据规模与约定
对于 $100\%$ 的数据,保证 $1\le n\le 2\times 10^5$,$1\le A,B\le 2\times 10^9$。
#### 说明
**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #4](https://hsin.hr/coci/archive/2006_2007/contest4_tasks.pdf) *T6 ISPITI***