皮特和鲍勃发明了一种新的有趣游戏。 Bob 拿一张纸并在其上定位笛卡尔坐标系,如下所示:点 (0, 0) 位于左下角,Ox 轴指向右侧,Oy 轴指向上方。 Pete 向 Bob 提出了三种类型的请求:
- 添加 x y — Bob 在纸上用坐标 (x, y) 标记一个点。对于这种类型的每个请求,可以保证在请求时点 (x, y) 尚未标记在 Bob 的工作表上。
- 删除 x y — Bob 在纸上擦除之前用坐标 (x, y) 标记的点。对于这种类型的每个请求,保证在请求时点 (x, y) 已经标记在 Bob 的工作表上。
- 查找 x y - Bob 在纸上找到所有标记的点,严格位于点 (x, y) 的上方和右侧。在这些点中,Bob选择最左边的一个,如果不唯一,他选择最下面的一个,并将其坐标提供给Pete。
当请求数量为 10、100 或 1000 时,Bob 设法回答了这些请求,但当数量增加到 2·105 时,Bob 无法应对。现在他需要一个能够满足皮特所有请求的程序。请帮助鲍勃!
输入
第一输入行包含数字 n (1 ≤ n ≤ 2·105) — 请求数量。接下来是n行——请求的描述。 add x y 描述添加点的请求,remove x y — 删除点的请求,find x y — 查找左下点的请求。输入文件中的所有坐标均为非负数且不超过 109。
输出
对于 find x y 类型的每个请求,在单独的行中输出其答案 - 最左边标记点中最底部的坐标,严格位于点 (x, y) 的上方和右侧。如果没有点严格位于点 (x, y) 的上方和右侧,则输出 -1。
示例
输入 #1
7 add 1 1 add 3 4 find 0 0 remove 1 1 find 0 0 add 1 1 find 0 0
输出 #1
1 1 3 4 1 1
输入 #2
13 add 5 5 add 5 6 add 5 7 add 6 5 add 6 6 add 6 7 add 7 5 add 7 6 add 7 7 find 6 6 remove 7 7 find 6 6 find 4 4
输出 #2
7 7 -1 5 5