题目描述

期末考试快到了，每个人都想用最少的努力通过考试，这当然不容易。Alice 认识到最好去请教一个成绩比他好的，每个人都想这样做。

我们规定一个学生成绩的好坏用两个整数 $A$ 和 $B$ 来表示，$A$ 表示对功课的理解力，$B$ 表示知识面。

作为班长，Alice 规定去请教的这个学生的理解力不得低于自己的理解力，同样知识面也不得低于自己的知识面，在这个基础上选择一个知识面（$B$ 值）跟自己差距最小的，如果还有多种选择，则在此基础上选择一个理解力（$A$ 值）跟自己差距最小的。

该学校不断有学生转进来，这给每个人的选择带来困难，现在请你来帮忙。

输入格式

输入的第一行包含一个整数 $n$，表示询问和转进学生的总数，接下来 $n$ 行，格式为以下两种之一：

• D A B，表示新转进一名学生，理解力为 $A$，知识面为 $B$；

• P i，要求输出第 $i$ 个转进的学生当前应该去请教谁（不能在后转进的学生中寻找）。

输出格式

对于每个 P i 询问，输出应该请教的学生的编号，学生的编号按照转进的顺序从 $1$ 开始编号，如果无人可以请教，则输出 NE。

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

2
4
4

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\leq A,B\leq 2\times 10^9$，不会存在两个学生的 $A$ 和 $B$ 都相等。