Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Lena and Queries

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLena 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.

Input

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.

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

Example

Input

7

3 1

1 2 3

3 1

1 -1 100

3 1

2 4

3 1

Output

EMPTY SET

5

99

5

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 06:36:29 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|