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 long double EPS = 1e-20;
const long long mod = 1000000007;
const long long INF = mod * mod + mod;
struct Line {
  long long a, b;
  long double inter(const Line& l) const {
    return (long double)(l.b - b) / (a - l.a);
  }
  Line() {}
  Line(long long a, long long b) : a(a), b(b) {}
  long long get(int x) { return a * 1ll * x + b; }
};
struct Hull {
  vector<Line> st;
  void push(const Line& l) {
    while ((int)(st).size() >= 2) {
      const Line& l1 = st[(int)(st).size() - 2];
      const Line& l2 = st[(int)(st).size() - 1];
      if (l2.a == l.a) {
        if (l.b > l2.b) {
          st.pop_back();
          continue;
        } else {
          return;
        }
      }
      long double x1 = l1.inter(l2);
      long double x2 = l2.inter(l);
      if (x2 < x1 + EPS) {
        st.pop_back();
      } else {
        break;
      }
    }
    st.push_back(l);
  }
  long long get_best(long long x) {
    int L = -1;
    int R = (int)(st).size() - 1;
    while (L < R - 1) {
      int M = (L + R) / 2;
      long double xx = st[M].inter(st[M + 1]);
      if (xx < x) {
        L = M;
      } else {
        R = M;
      }
    }
    long long ans = -INF;
    for (int i = max(0, L - 3); i < min((int)(st).size(), R + 4); ++i) {
      ans = max(ans, st[i].get(x));
    }
    return ans;
  }
};
const int MAXN = 301000;
vector<Hull> t(4 * MAXN);
vector<vector<Line>> vt(4 * MAXN);
void build(int v, int tl, int tr) {
  vt[v].push_back(Line(0, -INF));
  if (tl == tr) return;
  int tm = (tl + tr) / 2;
  build(v * 2, tl, tm);
  build(v * 2 + 1, tm + 1, tr);
}
void update(int v, int tl, int tr, int l, int r,
            std::pair<long long, long long> add) {
  if (l > r) return;
  if (l == tl && tr == r)
    vt[v].push_back(Line(add.first, add.second));
  else {
    int tm = (tl + tr) / 2;
    update(v * 2, tl, tm, l, min(r, tm), add);
    update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, add);
  }
}
long long get(int v, int tl, int tr, int pos, long long num) {
  if (tl == tr) return t[v].get_best(num);
  int tm = (tl + tr) / 2;
  if (pos <= tm)
    return max(t[v].get_best(num), get(v * 2, tl, tm, pos, num));
  else
    return max(t[v].get_best(num), get(v * 2 + 1, tm + 1, tr, pos, num));
}
int main() {
  int n;
  scanf("%d", &n);
  build(1, 0, n - 1);
  std::vector<int> type(n);
  std::vector<std::pair<int, int>> q(n);
  std::vector<int> num(n);
  std::vector<int> u(n, 0);
  for (int i = 0; i < n; i++) {
    scanf("%d", &type[i]);
    if (type[i] == 1) scanf("%d %d", &q[i].first, &q[i].second);
    if (type[i] == 2) scanf("%d", &num[i]);
    if (type[i] == 3) scanf("%d", &num[i]);
  }
  for (int i = n - 1; i >= 0; i--) {
    if (u[i]) continue;
    if (type[i] == 3) continue;
    if (type[i] == 2) {
      int l = num[i] - 1;
      update(1, 0, n - 1, l, i,
             make_pair((long long)q[l].first, (long long)q[l].second));
      u[l] = 1;
    }
    if (type[i] == 1) {
      update(1, 0, n - 1, i, n - 1,
             make_pair((long long)q[i].first, (long long)q[i].second));
    }
  }
  for (int i = 0; i < 4 * MAXN; i++) {
    if (vt[i].size() > 0) {
      sort((vt[i]).begin(), (vt[i]).end(), [](Line a, Line b) {
        return a.a < b.a || (a.a == b.a && a.b < b.b);
      });
      for (auto l : vt[i]) t[i].push(l);
    }
  }
  for (int i = 0; i < n; i++) {
    if (type[i] == 3) {
      long long ans = get(1, 0, n - 1, i, (long long)num[i]);
      if (ans == -INF)
        printf("EMPTY SET\n");
      else
        printf("%lld\n", ans);
    }
  }
}