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 = 300005;
struct line {
  long long a, b;
  int s, e;
  bool operator<(const line t) const { return a < t.a; }
};
struct convexhull_trick {
  int s, e;
  line deq[N];
  int size() { return e - s; }
  void insert(line v) {
    deq[e] = v;
    while (s + 1 < e &&
           (deq[e - 1].b - deq[e - 2].b) * (deq[e].a - deq[e - 1].a) <=
               (deq[e - 2].a - deq[e - 1].a) * (deq[e - 1].b - deq[e].b)) {
      deq[e - 1] = deq[e];
      e--;
    }
    e++;
  }
  long long query(int x) {
    while (s + 1 < e &&
           deq[s + 1].b - deq[s].b >= x * (deq[s].a - deq[s + 1].a))
      s++;
    return (deq[s].a * x + deq[s].b);
  }
  void clear() { s = e = 0; }
} cht;
struct ask {
  int x, p;
  bool operator<(const ask a) const {
    if (x != a.x) return x < a.x;
    return p < a.p;
  }
} Q[N];
int n, ln, qn, to[N], sn;
line L[N], sub[N];
int asked[N];
long long ans[N];
const long long inf = 9e18;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      ln++;
      scanf("%I64d%I64d", &L[ln].a, &L[ln].b);
      L[ln].s = i;
      L[ln].e = n;
      to[i] = ln;
    }
    if (type == 2) {
      int x;
      scanf("%d", &x);
      L[to[x]].e = i;
    }
    if (type == 3) {
      asked[i] = 1;
      ans[i] = -inf;
      qn++;
      scanf("%d", &Q[qn].x);
      Q[qn].p = i;
    }
  }
  sort(L + 1, L + ln + 1);
  sort(Q + 1, Q + qn + 1);
  int sz = 600;
  for (int t = 1; t <= n; t += sz) {
    int lt = t, rt = t + sz - 1;
    cht.clear();
    sn = 0;
    for (int i = 1; i <= ln; i++) {
      if (L[i].s <= lt && rt <= L[i].e)
        cht.insert(L[i]);
      else if ((lt <= L[i].s && L[i].s <= rt) || (lt <= L[i].e && L[i].e <= rt))
        sub[++sn] = L[i];
    }
    for (int i = 1; i <= qn; i++) {
      if (lt <= Q[i].p && Q[i].p <= rt) {
        if (cht.size() >= 1) {
          asked[Q[i].p] = 2;
          long long ret = cht.query(Q[i].x);
          ans[Q[i].p] = max(ans[Q[i].p], ret);
        }
        for (int j = 1; j <= sn; j++) {
          if (sub[j].s <= Q[i].p && Q[i].p <= sub[j].e) {
            asked[Q[i].p] = 2;
            long long ret = sub[j].a * Q[i].x + sub[j].b;
            ans[Q[i].p] = max(ans[Q[i].p], ret);
          }
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (asked[i] == 1) puts("EMPTY SET");
    if (asked[i] == 2) printf("%I64d\n", ans[i]);
  }
}