论坛帖子

说明

你是一个论坛的站长，论坛上有约 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。

样例输入

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

样例输出

10086
-1
12580
-1

提示

• 对于 ADD x y 操作，你可以将回复 ID 添加到一个容器（如 vector）中，按顺序存储每个帖子下的回复。
• 对于 QUERY x y 操作，首先检查帖子 x 是否存在至少 y 个回复，如果存在则输出第 y 个回复的 ID，否则输出 -1。

复杂度分析

• ​时间复杂度​：对于每次 ADD 操作，插入操作的时间复杂度为 O(1)。对于每次 QUERY 操作，访问和检查回复列表的时间复杂度为 O(1)。
• ​空间复杂度​：需要存储每个帖子的所有回复，所以空间复杂度为 O(N)，其中 N 是所有帖子的回复总数。