在 Mirko 的村庄里，现在是考试时间。每个人都想用尽可能少的努力通过考试，但这并不容易。Mirko 意识到，对他来说最好的办法是找到一个比他懂得多的人并向其学习。其他人也纷纷效仿，现在每个人都在寻找可以学习的对象。

我们可以用两个整数 $A$ 和 $B$ 来表示一个学生对考试的准备情况。数字 $A$ 代表学生对科目的理解程度，而数字 $B$ 与他们的知识量成正比。

作为村长，Mirko 决定，一个学生只有在另一个学生的两个数值都大于或等于该学生自身的数值时，才会向其寻求帮助（没有学生会向一个对科目理解不如自己或知识量比自己少的人寻求帮助）。

此外，学生们会尽力最小化知识量上的差距（这样学生就不会去打扰那些比自己优秀得多的人）。如果这个选择不唯一，他们会尽力最小化理解程度上的差距。

Mirko 的村庄最近成为了一个非常受欢迎的郊区，不断有新学生搬进来（正好赶上考试）。由于 Mirko 严格的规则，新来的学生感到很困惑，不知道该向谁求助。他们决定向邻村的一位程序员寻求帮助。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 200\,000$)，表示操作（查询和新学生到来）的总数。

接下来的 $N$ 行中，每行包含以下内容之一：

• "D A B"：一个知识水平为 $A$ 和 $B$ 的新学生搬了进来。
• "P i"：第 $i$ 个搬进来的学生想知道应该向谁寻求帮助。

数值 $A$ 和 $B$ 介于 $1$ 和 $2 \cdot 10^9$ 之间。没有两个学生的两个数值都相同。

输出格式

对于每个查询（即 "P i" 行），输出第 $i$ 个搬进来的学生应该向哪个学生寻求帮助。学生按照他们搬进村庄的顺序进行编号（从 $1$ 开始）。如果该学生无法得到任何人的帮助，输出 "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