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;
void addmod(int &a, long long b) {
  a = (a + b);
  if (a >= 1000000007) a -= 1000000007;
}
void mulmod(int &a, long long b) { a = (a * b) % 1000000007; }
int gi() {
  int a;
  scanf("%d", &a);
  return a;
}
long long gll() {
  long long a;
  scanf("%I64d", &a);
  return a;
}
struct line {
  int a, b;
  line() {}
  line(int a, int b) : a(a), b(b) {}
  double intersect(const line &l) const {
    assert(a != l.a);
    return (double)(l.b - b) / (a - l.a);
  }
  void set(int a, int b) { this->a = a, this->b = b; }
  long long get(long long x) { return a * x + b; }
};
class hull {
  bool mx;
  vector<line> vl, st;
  vector<double> xi;
  void push(const line &l) {
    double newx = -3e18;
    while (!st.empty()) {
      const line &l1 = st.back();
      if (l1.a == l.a) return;
      newx = l1.intersect(l);
      if (newx < xi.back() + 1e-9) {
        st.pop_back();
        xi.pop_back();
      } else
        break;
    }
    st.push_back(l);
    xi.push_back(newx);
  }

 public:
  hull(bool mx = false) : mx(mx) {}
  void add(int a, int b) { vl.push_back(line(a, b)); }
  void precalc() {
    static auto cmp = [this](line &a, line &b) {
      if (a.a != b.a) return mx ? a.a < b.a : a.a > b.a;
      return mx ? a.b > b.b : a.b < b.b;
    };
    if (vl.empty()) return;
    st.clear(), xi.clear();
    sort(vl.begin(), vl.end(), cmp);
    for (auto a : vl) push(a);
  }
  long long get(int x) {
    if (st.empty()) return -3e18;
    int i = upper_bound(xi.begin(), xi.end(), x) - xi.begin() - 1;
    return st[i].get(x);
  }
};
class bitree {
  const int &n;
  vector<hull> t;

 public:
  bitree(const int &n) : n(n), t(4 * n, hull(true)) {}
  void build() { build(1, 0, n - 1); }
  void build(int v, int l, int r) {
    t[v].precalc();
    if (l == r) {
      return;
    }
    int mid = (l + r) / 2, nv = v * 2;
    build(nv, l, mid);
    build(nv + 1, mid + 1, r);
  }
  void update(int ql, int qr, pair<int, int> val) {
    update(ql, qr, val, 1, 0, n - 1);
  }
  void update(int ql, int qr, pair<int, int> val, int v, int l, int r) {
    if (ql > qr) return;
    if (ql > r || qr < l) return;
    if (ql <= l && qr >= r) {
      t[v].add(val.first, val.second);
      return;
    }
    int mid = (l + r) / 2, nv = v * 2;
    update(ql, qr, val, nv, l, mid);
    update(ql, qr, val, nv + 1, mid + 1, r);
  }
  long long query(int ql, int qr, int x) {
    return query(ql, qr, x, 1, 0, n - 1);
  }
  long long query(int ql, int qr, int x, int v, int L, int R) {
    if (ql > R || qr < L) return -3e18;
    long long ans = t[v].get(x);
    if (ql <= L && qr >= R) return ans;
    int MID = (L + R) / 2, nv = v * 2;
    return max(ans, max(query(ql, qr, x, nv, L, MID),
                        query(ql, qr, x, nv + 1, MID + 1, R)));
  }
};
int main() {
  int n = gi(), v;
  bitree t(n);
  vector<pair<int, int> > vpi(n);
  vector<bool> vb(n, false);
  vector<int> ty(n, 0);
  for (int i = 0; i < n; i++) {
    ty[i] = gi();
    if (ty[i] == 1) {
      vpi[i].first = gi(), vpi[i].second = gi();
    } else if (ty[i] == 2) {
      v = gi() - 1;
      vb[v] = true;
      t.update(v, i, vpi[v]);
    } else {
      vpi[i].first = gi();
    }
  }
  for (int i = 0; i < n; i++)
    if (ty[i] == 1 && !vb[i]) {
      t.update(i, n - 1, vpi[i]);
    }
  t.build();
  for (int i = 0; i < n; i++)
    if (ty[i] == 3) {
      long long ans = t.query(i, i, vpi[i].first);
      if (ans == -3e18)
        cout << "EMPTY SET" << endl;
      else
        cout << ans << endl;
    }
  return 0;
}