CF678F.Lena and Queries

Lena is a programmer. She got a task to solve at work.

There is an empty set of pairs of integers and n queries to process. Each query is one of three types:

1. Add a pair (a, b) to the set.
2. Remove a pair added in the query number i. All queries are numbered with integers from 1 to n.
3. For a given integer q find the maximal value x·q + y over all pairs (x, y) from the set.

Help Lena to process the queries.

莉娜是一名程序员，她在工作中接到一项任务。

初始时有一个空的整数对集合，需要处理 $ n $ 个查询。每个查询属于以下三种类型之一：

1. 将整数对 $ (a,,b) $ 加入集合；
2. 删除在第 $ i $ 个查询中加入的整数对（所有查询按整数编号，编号范围为 $ 1 $ 到 $ n $）；
3. 对于给定的整数 $ q $，在集合中所有整数对 $ (x,,y) $ 上求表达式 $ x \cdot q + y $ 的最大值。

请帮助莉娜处理这些查询。

The first line of input contains integer n (1 ≤ n ≤ 3·105) — the number of queries.

Each of the next n lines starts with integer t (1 ≤ t ≤ 3) — the type of the query.

A pair of integers a and b ( - 109 ≤ a, b ≤ 109) follows in the query of the first type.

An integer i (1 ≤ i ≤ n) follows in the query of the second type. It is guaranteed that i is less than the number of the query, the query number i has the first type and the pair from the i-th query is not already removed.

An integer q ( - 109 ≤ q ≤ 109) follows in the query of the third type.

输入的第一行包含一个整数 $ n $（$ 1 \leq n \leq 3 \cdot 10^5 $）—— 表示查询的次数。

接下来的 $ n $ 行，每行以一个整数 $ t $（$ 1 \leq t \leq 3 $）开头 —— 表示该查询的类型。

对于第一类查询，其后跟随一对整数 $ a $ 和 $ b $（$ -10^9 \leq a, b \leq 10^9 $）。

对于第二类查询，其后跟随一个整数 $ i $（$ 1 \leq i \leq n $）。保证 $ i $ 小于当前查询的序号，且第 $ i $ 个查询为第一类查询，且第 $ i $ 个查询中的数对尚未被删除。

对于第三类查询，其后跟随一个整数 $ q $（$ -10^9 \leq q \leq 10^9 $）。

For the queries of the third type print on a separate line the desired maximal value of x·q + y.

If there are no pairs in the set print "EMPTY SET".

对于第三种查询，在单独一行输出所求的 $x \cdot q + y$ 的最大值。

如果集合中没有数对，则输出 "EMPTY SET"。