#P678F. Lena and Queries
-
ID: 4217
Type: RemoteJudge
4000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 9
Uploaded By:
Hydro
Tags> Lena and Queries
Description
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:
- Add a pair (a, b) to the set.
- Remove a pair added in the query number i. All queries are numbered with integers from 1 to n.
- 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·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.
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".
Input
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.
Output
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".
Samples
7
3 1
1 2 3
3 1
1 -1 100
3 1
2 4
3 1
EMPTY SET
5
99
5