#7144. 【基础】论坛帖子 普及−

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

题目描述

你是一个论坛的站长,你们论坛有约10万个帖子,每个帖子编号为1-100000。每个帖子里面又有若干个回复。现在告诉你每个帖子下面的回复人的ID(ID的范围为1-100000)现在你要写一个程序,支持插入操作,即ADD x y 代表编号为x的帖子有一个ID为y的人回复。支持查询操作,即QUERY x y 代表查询编号为x的帖子第y个回复的人的ID。

输入格式

第1行一个整数N,代表有N次询问(1<=N<=100000)
第2行到第N+1行代表N次询问的内容,每行为以下2种格式之一:
ADD x y 新增加了一个回复,代表编号为x的帖子有一个ID为y的人回复
QUERY x y 代表查询编号为x的帖子第y个回复的人的ID
保证1<=x<=100000,1<=y<=100000

输出格式

对于每个QUERY的查询,每次输出占一行,代表编号为x的帖子第y个回复的人的ID,如果编号为x的帖子总的回复数小于y,则输出-1。

样例

样例输入1

8
ADD 10 10086
ADD 10 10010
QUERY 10 1
QUERY 88888 1
ADD 88888 10010
ADD 88888 12580
QUERY 88888 2
QUERY 88888 3

样例输出1

10086 
-1 
12580 
-1