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;
int const inf = 1000 * 1000 * 1000;
long long const inf64 = 1ll * inf * inf;
template <class T>
struct ConvexHullTrick {
  size_t sz;
  vector<pair<T, T> > Lines, st;
  ConvexHullTrick() { sz = 0; }
  bool check(pair<T, T> a, pair<T, T> b) const {
    if (a.second < 0) a.first = -a.first, a.second = -a.second;
    if (b.second < 0) b.first = -b.first, b.second = -b.second;
    return 1ll * a.first * b.second < 1ll * b.first * a.second;
  }
  void add_line(pair<T, T> L) {
    pair<T, T> l1, l2;
    while (!st.empty() && st.back().first == L.first) st.pop_back();
    while ((int)st.size() > 1) {
      l1 = st[(int)st.size() - 2];
      l2 = st[(int)st.size() - 1];
      if (check({l1.second - l2.second, l2.first - l1.first},
                {l2.second - L.second, L.first - l2.first}))
        break;
      st.pop_back();
    }
    st.push_back(L);
    sz = st.size();
  }
  ConvexHullTrick(vector<pair<T, T> > _lines) : Lines(_lines) {
    sort((Lines).begin(), (Lines).end());
    for (size_t i = 0; i < Lines.size(); i++) add_line(Lines[i]);
  }
  bool check(size_t i, T x) const {
    pair<T, T> l1, l2;
    l1 = st[i - 1];
    l2 = st[i];
    return !check({x, 1}, {l1.second - l2.second, l2.first - l1.first});
  }
  T get(T x) const {
    if (sz == 1 || !check(1, x)) return st[0].first * x + st[0].second;
    size_t bl, br, bm;
    bl = 1;
    br = sz - 1;
    while (br - bl > 1) {
      bm = (bl + br) >> 1;
      if (check(bm, x))
        bl = bm;
      else
        br = bm - 1;
    }
    return max(st[bl].first * x + st[bl].second,
               st[br].first * x + st[br].second);
  }
  void show() {
    cout << "sz = " << sz << " : \n";
    for (int i = 0; i < sz; i++) {
      cout << st[i].first << ' ' << st[i].second << "\n";
    }
    for (int i = 1; i < sz; i++) {
      pair<double, double> l1, l2;
      l1 = st[i - 1];
      l2 = st[i];
      cout << fixed << setprecision(3)
           << (l1.second - l2.second) / (l2.first - l1.first) << " ";
    }
    cout << "\n\n";
  }
};
long long const MIN_VALUE = -inf64 - inf - 1;
int n;
vector<char> del;
vector<pair<int, int> > Lines;
vector<int> type, que;
vector<vector<pair<long long, long long> > > t_lines;
vector<ConvexHullTrick<long long> > t_hull;
void add(int v, int tl, int tr, int l, int r, pair<long long, long long> line) {
  if (l <= tl && tr <= r) {
    t_lines[v].push_back(line);
  } else {
    int tm = (tl + tr) >> 1;
    if (l <= tm) add(v * 2 + 1, tl, tm, l, r, line);
    if (r > tm) add(v * 2 + 2, tm + 1, tr, l, r, line);
  }
}
long long get(int v, int tl, int tr, int pos, long long x) {
  long long res = MIN_VALUE;
  if (t_hull[v].sz > 0) res = max(res, t_hull[v].get(x));
  if (tl < tr) {
    int tm = (tl + tr) >> 1;
    if (pos <= tm)
      res = max(res, get(v * 2 + 1, tl, tm, pos, x));
    else
      res = max(res, get(v * 2 + 2, tm + 1, tr, pos, x));
  }
  return res;
}
bool solve() {
  scanf("%d", &n);
  del.resize(n);
  Lines.resize(n);
  que.resize(n);
  type.resize(n);
  t_lines.resize(4 * n);
  t_hull.resize(4 * n);
  for (int x, i = 0; i < n; i++) {
    scanf("%d", &type[i]);
    if (type[i] == 1) {
      scanf("%d %d", &Lines[i].first, &Lines[i].second);
    } else if (type[i] == 2) {
      scanf("%d", &x);
      x--;
      del[x] = 1;
      add(0, 0, n - 1, x, i, Lines[x]);
    } else {
      scanf("%d", &que[i]);
    }
  }
  for (int i = 0; i < n; i++) {
    if (type[i] == 1 && !del[i]) {
      add(0, 0, n - 1, i, n - 1, Lines[i]);
    }
  }
  for (int i = 0; i < 4 * n; i++) {
    if (t_lines[i].empty()) continue;
    t_hull[i] = ConvexHullTrick<long long>(t_lines[i]);
  }
  for (int i = 0; i < n; i++) {
    if (type[i] == 3) {
      long long x = get(0, 0, n - 1, i, que[i]);
      if (x == MIN_VALUE)
        printf("EMPTY SET\n");
      else
        printf("%I64d\n", x);
    }
  }
  return true;
}
int main() {
  solve();
  return 0;
}