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 N = 3e5 + 10;
const int64_t inf = 1LL << 60;
inline int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return f ? -x : x;
}
struct node {
  int a, b, l, r;
  inline node(int _a = 0, int _b = 0, int _l = 0, int _r = 0) {
    a = _a, b = _b, l = _l, r = _r;
  }
} pt[N];
int id[N];
struct query {
  int x, p, id;
  inline query(int _x = 0, int _p = 0, int _id = 0) {
    x = _x, p = _p, id = _id;
  }
} q[N];
struct point {
  int x, y;
  inline point(int _x = 0, int _y = 0) { x = _x, y = _y; }
  inline friend point operator-(point a, point b) {
    return point(a.x - b.x, a.y - b.y);
  }
  inline friend int64_t operator*(point a, point b) {
    return 1LL * a.x * b.y - 1LL * a.y * b.x;
  }
};
inline int64_t cross(point a, point b, point c) { return (a - b) * (c - b); }
inline int64_t calc(point a, int k) { return 1LL * a.x * k + a.y; }
struct convex {
  std::vector<point> vec;
  int pos;
  inline void push(point a) {
    while (vec.size() > 1 && cross(vec[vec.size() - 2], vec.back(), a) <= 0)
      vec.pop_back();
    vec.emplace_back(a);
  }
  inline int64_t ask(int k) {
    if (vec.empty()) return -inf;
    while (pos + 1 < vec.size() && calc(vec[pos], k) <= calc(vec[pos + 1], k))
      ++pos;
    return calc(vec[pos], k);
  }
} con[N << 2];
inline void ins(int k, int l, int r, int ql, int qr, point pt) {
  if (l > r || ql > r || l > qr) return;
  if (ql <= l && r <= qr) return con[k].push(pt);
  int mid = (l + r) >> 1;
  ins(k << 1, l, mid, ql, qr, pt);
  ins(k << 1 | 1, mid + 1, r, ql, qr, pt);
}
inline int64_t ask(int k, int l, int r, int p, int x) {
  int64_t ans = con[k].ask(x);
  if (l == r) return ans;
  int mid = (l + r) >> 1;
  if (p <= mid)
    ans = std::max(ans, ask(k << 1, l, mid, p, x));
  else
    ans = std::max(ans, ask(k << 1 | 1, mid + 1, r, p, x));
  return ans;
}
int64_t ans[N];
int main() {
  int n = read(), m = 0, t = 0;
  for (int i = 1; i <= n; ++i) {
    int op = read();
    if (op == 1) {
      int a = read(), b = read();
      pt[++m] = node(a, b, i, n), id[i] = m;
    }
    if (op == 2) pt[id[read()]].r = i;
    if (op == 3) ++t, q[t] = query(read(), i, t);
  }
  std::sort(pt + 1, pt + m + 1, [&](node a, node b) {
    return a.a < b.a || a.a == b.a && a.b < b.b;
  });
  for (int i = 1; i <= m; ++i)
    ins(1, 1, n, pt[i].l, pt[i].r, point(pt[i].a, pt[i].b));
  std::sort(q + 1, q + t + 1, [&](query a, query b) { return a.x < b.x; });
  for (int i = 1; i <= t; ++i) ans[q[i].id] = ask(1, 1, n, q[i].p, q[i].x);
  for (int i = 1; i <= t; ++i)
    if (ans[i] == -inf)
      puts("EMPTY SET");
    else
      printf("%lld\n", ans[i]);
  return 0;
}