← 返回题目列表

Codeforces · 678/F

F. 莉娜和查询

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

Lena 是一名程序员。她在工作中有一项任务需要解决。

有一组空的整数对和 n 个查询要处理。每个查询都是以下三种类型之一:

1. 将一对 (a, b) 添加到集合中。
2.删除查询号i中添加的一对。所有查询均使用 1 到 n 的整数进行编号。
3. 对于给定的整数 q,找到集合中所有对 (x, y) 的最大值 x·q + y。

帮助 Lena 处理查询。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 3·105) — 查询数。

接下来的 n 行均以整数 t (1 ≤ t ≤ 3) 开头 — 查询的类型。

第一类查询中紧随一对整数 a 和 b (- 109 ≤ a, b ≤ 109)。

第二类型的查询中跟随整数i(1≤i≤n)。保证i小于查询的数量,查询编号i具有第一类型并且来自第i个查询的对尚未被删除。

第三类查询中跟随整数q(-109≤q≤109)。

输出

对于第三种类型的查询,在单独的行上打印所需的 x·q + y 的最大值。

如果集合中没有对,则打印“EMPTY SET”。

示例

输入 #1

7
3 1
1 2 3
3 1
1 -1 100
3 1
2 4
3 1

输出 #1

EMPTY SET
5
99
5