← 返回题目列表

Codeforces · 19/D

D. 积分

中文机器翻译题面 查看原题

皮特和鲍勃发明了一种新的有趣游戏。 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