Problem: 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.

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

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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 300100;
const int M = 1000100;
const int K = 200100;
const int oo = 2e9;
const long long OO = 2e18;
const int PW = 20;
const int md = 1000000007;
int tp[N], q, BLOCK, tt, siz, TT, mrk[N], vc[N], vec[N];
long long x[N], y[N], vl[N], fr[N], X[N], Y[N];
multiset<pair<int, int> > st;
inline long long divide(long long tp, long long a, long long b) {
  if (b == 0) {
    if (tp >= 0)
      return oo;
    else
      return -oo;
  }
  long long res = a / b, ost = a % b;
  if ((a <= 0 && b < 0) || (a >= 0 && b > 0))
    return res + bool(ost);
  else
    return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> q;
  st.clear();
  for (int i = 0; i < q; i++) {
    cin >> tp[i];
    mrk[i] = oo;
    if (tp[i] == 1)
      cin >> x[i] >> y[i];
    else
      cin >> vl[i];
  }
  BLOCK = 2500;
  for (int it = 0; it < q; it += BLOCK) {
    int l = it, r = min(it + BLOCK, q);
    TT = 0;
    for (int i = l; i < r; i++)
      if (tp[i] == 2) {
        int nm = vl[i] - 1;
        mrk[nm] = i;
        vec[TT++] = nm;
        if (nm < l) st.erase(st.find(make_pair(x[nm], y[nm])));
      }
    if (TT > 0) reverse(vec, vec + TT);
    siz = 0;
    for (auto cr : st) {
      if (!siz) {
        siz = 1;
        fr[1] = -OO;
        X[1] = cr.first;
        Y[1] = cr.second;
      } else {
        long long CX = cr.first, CY = cr.second;
        while (siz > 1) {
          long long pos = divide(CX, CY - Y[siz - 1], X[siz - 1] - CX);
          if (pos > fr[siz]) break;
          siz--;
        }
        siz++;
        fr[siz] = divide(CX, CY - Y[siz - 1], X[siz - 1] - CX);
        X[siz] = CX;
        Y[siz] = CY;
      }
    }
    tt = 0;
    for (int i = l; i < r; i++)
      if (tp[i] == 1) {
        vc[tt++] = i;
        if (mrk[i] == oo) st.emplace(x[i], y[i]);
      } else if (tp[i] == 3) {
        long long res = -OO;
        bool was = 0;
        if (siz > 0) {
          was = 1;
          int ps = upper_bound(fr + 1, fr + siz + 1, vl[i]) - fr - 1;
          res = max(res, X[ps] * vl[i] + Y[ps]);
        }
        for (int j = 0; j < tt; j++) {
          if (mrk[vc[j]] > i) {
            was = 1;
            res = max(res, x[vc[j]] * vl[i] + y[vc[j]]);
          }
        }
        for (int j = 0; j < TT; j++) {
          if (vec[j] < i) {
            was = 1;
            res = max(res, x[vec[j]] * vl[i] + y[vec[j]]);
          }
        }
        if (!was)
          cout << "EMPTY SET\n";
        else
          cout << res << '\n';
      } else
        TT--;
  }
  return 0;
}