ispiti

时间限制:10s      空间限制:128MB

题目描述

期末考试快到了,每个人都想用最少的努力通过考试,这当然不容易。Alice认识到最好去请教一个成绩比他好的,每个人都想这样做。
我们规定一个学生成绩的好坏用两个整数A和B来表示,A表示对功课的理解力,B表示知识面。
作为班长,Alice规定去请教的这个学生的理解力不得低于自己的理解力,同样知识面也不得低于自己的知识面,在这个基础上选择一个知识面(B值)跟自己差距最小的,如果还有多种选择,则在此基础上选择一个理解力(A值)跟自己差距最小的。
该学校不断有学生转进来,这给每个人的选择带来困难,现在请你来帮忙。


输入格式

输入的第一行包含一个整数N(1<=N<=200000),表示询问和转进学生的总数,接下来N行,格式为以下两种之一:
·“D A B”,表示新转进一名学生,理解力为A,知识面为B;
·P i”,要求输出第i个转进的学生当前应该去请教谁(不能在后转进的学生中寻找)。
数据保证:1<=A,B<=2*10^9,不会存在两个学生的AB都相等。


输出格式

 
对于每个“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

提示

没有写明提示


题目来源

没有写明来源