5007 - [COCI 2006-2007 #4] ISPITI

考试在即,学生们赶快加紧了复习的进度。每个学生都有两个能力系数 A\ B

我们认为一个学生会向另一个学生求助,当且仅当另一个学生的 AB 都不小于这个学生。

现在给出 4n 条指令,有以下两种类型:

  • D A B 来了一个学生,他的两个能力系数为 AB

  • P ii 个学生想知道找谁帮忙。为了不大材小用,如果有多人可以求助,他会首先选择系数 B 相差最小的。如果 B 相同,则首选 A 相差最小的。

其中学生的编号由入场的顺序从 1 开始依次编排。

输入

输入第一行为一个整数 n ,表示指令的总数。

接下来的 n 行,每行一个指令,具体格式参照题目描述。

保证不会存在任意两个学生的两个指数都相同。

输出

对于每一个 P i,输出一个整数,为第 i 个学生想向哪个编号的学生求助。如果这个学生没有可以求助的对象,则输出 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

提示

对于 100\% 的数据,保证 1\le n\le 2\times 10^5

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题