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>
const int MAX_N = (int)3e5 + 123;
const double eps = 1e-6;
const int mod = 2017;
using namespace std;
struct Line {
  int k, b;
  Line() {}
  Line(int k, int b) : k(k), b(b) {}
  bool operator<(const Line &first) const {
    if (k != first.k) return k < first.k;
    return b > first.b;
  }
  double inter(Line first) { return 1.0 * (first.b - b) / (k - first.k); }
  long long int best(int q) { return 1ll * k * q + b; }
};
int n;
vector<Line> t[4 * MAX_N], st[4 * MAX_N];
void update(int l, int r, Line val, int v = 1, int tl = 1, int tr = n) {
  if (tl > r || l > tr) return;
  if (tl >= l && tr <= r) {
    t[v].push_back(val);
    return;
  }
  int tm = (tl + tr) / 2;
  update(l, r, val, v * 2, tl, tm);
  update(l, r, val, v * 2 + 1, tm + 1, tr);
}
void upd(vector<Line> &st, vector<Line> &now) {
  sort(now.begin(), now.end());
  for (auto i : now) {
    if (!st.empty() && st.back().k == i.k) continue;
    while ((int)((st).size()) > 1 &&
           i.inter(st[(int)((st).size()) - 2]) <
               st.back().inter(st[(int)((st).size()) - 2]))
      st.pop_back();
    st.push_back(i);
  }
}
long long int find_best(vector<Line> &st, int q) {
  if (st.empty()) return (-1ll) * (long long int)2e18;
  int l = 0, r = (int)((st).size()) - 2, mid = -1, ans = 0;
  while (l <= r) {
    mid = (l + r) / 2;
    if (st[mid].best(q) <= st[mid + 1].best(q)) {
      ans = mid + 1;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  long long int opt = (long long int)-2e18;
  for (int i = max(0, ans - 0); i < min((int)((st).size()), ans + 1); i++)
    opt = max(opt, st[i].best(q));
  return opt;
}
vector<int> top;
int tp[MAX_N], q[MAX_N];
Line h[MAX_N];
long long int ans[MAX_N];
set<int> last;
void go(int v = 1, int tl = 1, int tr = n) {
  upd(st[v], t[v]);
  top.push_back(v);
  if (tl == tr) {
    if (tp[tl] != 3) {
      top.pop_back();
      return;
    }
    ans[tl] = (-1ll) * (long long int)2e18;
    for (auto i : top) {
      ans[tl] = max(ans[tl], find_best(st[i], q[tl]));
    }
    top.pop_back();
    return;
  }
  int tm = (tl + tr) / 2;
  go(v * 2, tl, tm), go(v * 2 + 1, tm + 1, tr);
  top.pop_back();
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &tp[i]);
    if (tp[i] == 1) {
      scanf("%d%d", &h[i].k, &h[i].b);
      last.insert(i);
    } else if (tp[i] == 2) {
      scanf("%d", &q[i]);
      update(q[i], i - 1, h[q[i]]);
      last.erase(q[i]);
    } else
      scanf("%d", &q[i]);
  }
  for (auto i : last) update(i, n, h[i]);
  go();
  for (int i = 1; i <= n; i++)
    if (tp[i] == 3) {
      if (ans[i] == (-2ll) * (long long int)1e18)
        printf("EMPTY SET\n");
      else
        printf(
            "%lld"
            "\n",
            ans[i]);
    }
  return 0;
}