Description

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

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

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

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

Format

Input

输入的第一行包含一个整数N（1<=N<=200000），表示询问和转进学生的总数，接下来N行，格式为以下两种之一：

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

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

数据保证：1<=A,B<=2*10^9，不会存在两个学生的A和B都相等。

Output

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

Samples

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

2
4
4