A10410 | 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.

The first line of input contains integer $n$ ( $1<=n<=3·10^{5}$ ) — 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$ ( $-10^{9}<=a,b<=10^{9}$ ) 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$ ( $-10^{9}<=q<=10^{9}$ ) follows in the query of the third type.

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".