logo AlgoBeat OnlineJudge
登录 注册

#102773. [BZOJ 2773] ispiti

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

样例输入 #1

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

样例输出 #1

2
4
4

数据范围与提示

对于 的数据,,不会存在两个学生的 都相等。