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 inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 0x7fffffffffffffff;
const double eps = 1e-10;
unsigned int seed = 19260817;
const unsigned int _RAND_MAX_ = 4294967295u;
__inline__ __attribute__((always_inline)) unsigned int Rand() {
  return seed = seed * 998244353u + 1000000007u;
}
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp abs(const _Tp &a) {
  return a > 0 ? a : -a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp max(const _Tp &a, const _Tp &b) {
  return a < b ? b : a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp min(const _Tp &a, const _Tp &b) {
  return a < b ? a : b;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmin(_Tp &a, const _Tp &b) {
  (b < a) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) bool _cmp(const _Tp &a,
                                                    const _Tp &b) {
  return abs(a - b) <= eps;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void read(_Tp &x) {
  register char ch(getchar());
  bool f(false);
  while (ch < 48 || ch > 57) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (ch >= 48 && ch <= 57)
    x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  if (f) x = -x;
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
__inline__ __attribute__((always_inline)) int read_str(char *s) {
  register char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  register char *tar = s;
  *tar = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *(++tar) = ch, ch = getchar();
  return tar - s + 1;
}
const int N = 300005;
bool used[N];
long long ans[N];
struct vec {
  long long x, y;
  __inline__ __attribute__((always_inline)) bool operator<(const vec &o) const {
    return x == o.x ? y < o.y : x < o.x;
  }
  __inline__ __attribute__((always_inline)) vec operator+(const vec &o) const {
    return {x + o.x, y + o.y};
  }
  __inline__ __attribute__((always_inline)) vec operator-(const vec &o) const {
    return {x - o.x, y - o.y};
  }
  __inline__ __attribute__((always_inline)) long long operator*(
      const vec &o) const {
    return x * o.y - y * o.x;
  }
} E[N];
struct node {
  int k, id;
  __inline__ __attribute__((always_inline)) bool operator<(
      const node &o) const {
    return k > o.k;
  }
};
struct seg_tr {
  struct Node {
    int ls, rs;
    std::vector<vec> v;
    std::vector<node> V;
  } f[N << 1];
  int node_cnt;
  int build(int l, int r) {
    int cur = ++node_cnt;
    if (l == r) return cur;
    int mid = (l + r) >> 1;
    f[cur].ls = build(l, mid);
    f[cur].rs = build(mid + 1, r);
    return cur;
  }
  void Update(int L, int R, int l, int r, int cur, const vec &o) {
    if (L <= l && r <= R) {
      f[cur].v.push_back(o);
      return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) Update(L, R, l, mid, f[cur].ls, o);
    if (R > mid) Update(L, R, mid + 1, r, f[cur].rs, o);
  }
  void Update(int pos, int l, int r, int cur, const node &o) {
    f[cur].V.push_back(o);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid)
      Update(pos, l, mid, f[cur].ls, o);
    else
      Update(pos, mid + 1, r, f[cur].rs, o);
  }
  vec _q[N];
  int _l, _r;
  void Query(int l, int r, int cur) {
    std::sort(f[cur].v.begin(), f[cur].v.end());
    std::sort(f[cur].V.begin(), f[cur].V.end());
    _l = 1, _r = 0;
    for (auto it : f[cur].v) {
      while (_r - _l >= 1 && (_q[_r] - _q[_r - 1]) * (it - _q[_r]) >= 0) --_r;
      _q[++_r] = it;
    }
    for (auto it : f[cur].V) {
      while (_r - _l >= 1 &&
             (_q[_l + 1].y - _q[_l].y) >= (_q[_l + 1].x - _q[_l].x) * it.k)
        ++_l;
      if (_l != _r + 1) {
        chmax(ans[it.id], -_q[_l].x * it.k + _q[_l].y);
      }
    }
    if (l == r) return;
    int mid = (l + r) >> 1;
    Query(l, mid, f[cur].ls);
    Query(mid + 1, r, f[cur].rs);
  }
} tr;
bool type[N];
int main() {
  int _;
  read(_);
  tr.build(1, _);
  int opt, x;
  for (int i = 1; i <= _; ++i) {
    read(opt);
    if (opt == 1) {
      read(E[i].x, E[i].y);
      used[i] = 1;
    } else if (opt == 2) {
      read(x);
      used[x] = 0;
      tr.Update(x, i, 1, _, 1, E[x]);
    } else {
      type[i] = true;
      ans[i] = -3000000000000000000LL;
      read(x);
      tr.Update(i, 1, _, 1, {-x, i});
    }
  }
  for (int i = 1; i <= _; ++i) {
    if (used[i]) {
      tr.Update(i, _, 1, _, 1, E[i]);
    }
  }
  tr.Query(1, _, 1);
  for (int i = 1; i <= _; ++i) {
    if (type[i]) {
      if (ans[i] <= -3000000000000000000LL)
        printf("EMPTY SET\n");
      else
        printf("%lld\n", ans[i]);
    }
  }
  return 0;
}