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;
bool Q;
struct Line {
  mutable long long k, m, p;
  bool operator<(const Line& o) const { return Q ? p < o.p : k < o.k; }
};
struct HullDynamic : multiset<Line> {
  const long long inf = LLONG_MAX;
  long long div(long long a, long long b) {
    return a / b - ((a ^ b) < 0 && a % b);
  }
  bool isect(iterator x, iterator y) {
    if (y == end()) {
      x->p = inf;
      return false;
    }
    if (x->k == y->k)
      x->p = x->m > y->m ? inf : -inf;
    else
      x->p = div(y->m - x->m, x->k - y->k);
    return x->p >= y->p;
  }
  void add(long long k, long long m) {
    auto z = insert({k, m, 0}), y = z++, x = y;
    while (isect(y, z)) z = erase(z);
    if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
    while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
  }
  long long query(long long x) {
    assert(!empty());
    Q = 1;
    auto l = *lower_bound({0, 0, x});
    Q = 0;
    return l.k * x + l.m;
  }
};
struct Query {
  int in, out, type;
  long long a, b;
  Query(int in, int out, int type, long long a, long long b)
      : in(in), out(out), type(type), a(a), b(b) {}
};
const int ms = 3e5 + 5;
int n;
HullDynamic seg[4 * ms];
void add(int l, int r, pair<long long, long long> val, int on = 1, int L = 0,
         int R = n - 1) {
  if (r < L || l > R) return;
  if (l <= L && R <= r) {
    seg[on].add(val.first, val.second);
  } else {
    int mid = (L + R) / 2;
    add(l, r, val, 2 * on, L, mid);
    add(l, r, val, 2 * on + 1, mid + 1, R);
  }
}
long long query(int pos, long long x, int on = 1, int L = 0, int R = n - 1) {
  if (L > pos || R < pos) {
    return -3e18;
  }
  if (L == R) {
    if (seg[on].empty()) return -3e18;
    return seg[on].query(x);
  } else {
    int mid;
    long long z1, z2, z3;
    mid = (L + R) / 2;
    z1 = z2 = z3 = -3e18;
    if (!seg[on].empty()) z1 = seg[on].query(x);
    z2 = query(pos, x, 2 * on, L, mid);
    z3 = query(pos, x, 2 * on + 1, mid + 1, R);
    return max(z1, max(z2, z3));
  }
}
int32_t main() {
  scanf("%d", &n);
  map<pair<int, int>, int> m;
  vector<pair<int, int>> aux(n);
  vector<Query> q;
  for (int t = 0; t < n; ++t) {
    int k;
    scanf("%d", &k);
    long long a, b;
    if (k == 1) {
      scanf("%lld %lld", &a, &b);
      aux[t] = {a, b};
      m[{a, b}] = t;
    } else if (k == 2) {
      scanf("%lld", &a);
      a--;
      int in = m[aux[a]], out = t;
      q.emplace_back(in, out, 0, aux[a].first, aux[a].second);
      m.erase(aux[a]);
    } else {
      scanf("%lld", &a);
      q.emplace_back(t, t, 1, a, 0);
    }
  }
  for (auto x : m) {
    q.emplace_back(x.second, n - 1, 0, x.first.first, x.first.second);
  }
  n += 3;
  for (auto qr : q) {
    if (qr.type == 0) {
      add(qr.in, qr.out, {qr.a, qr.b});
    }
  }
  for (auto qr : q) {
    if (qr.type == 1) {
      long long ans = query(qr.in, qr.a);
      if (ans == -3e18) {
        printf("EMPTY SET\n");
      } else {
        printf("%lld\n", ans);
      }
    }
  }
  return 0;
}