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;
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "Yes" : "No");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  x += y;
  if (x >= mod) x -= mod;
}
void et() {
  puts("-1");
  exit(0);
}
struct qy {
  int t, a, b, id, q;
  void rd() {
    scanf("%d", &t);
    if (t == 1)
      scanf("%d%d", &a, &b);
    else if (t == 2) {
      scanf("%d", &id);
    } else
      scanf("%d", &q);
  }
} q[300155];
struct Line {
  long long a, b;
  long long get(long long x) { return a * x + b; }
};
struct ConvexHull {
  int size = 0, preQueryPos = 0;
  vector<Line> hull;
  ConvexHull() { size = 0; }
  void clear() {
    size = 0;
    preQueryPos = 0;
    hull.clear();
  }
  bool is_bad(int curr, int prev, int next) {
    Line c = hull[curr], p = hull[prev], n = hull[next];
    return (c.b - n.b) * (c.a - p.a) <= (p.b - c.b) * (n.a - c.a);
  }
  void add_line(long long a, long long b) {
    hull.push_back((Line){a, b});
    size++;
    while (size > 2 && is_bad(size - 2, size - 3, size - 1)) {
      hull[size - 2] = hull[size - 1];
      size--;
      hull.pop_back();
    }
  }
  long long query(long long x) {
    if (size == 0) return -(1LL << 60);
    int l = -1, r = size - 1;
    while (r - l > 1) {
      int m = (l + r) / 2;
      if (hull[m].get(x) <= hull[m + 1].get(x))
        l = m;
      else
        r = m;
    }
    long double z = hull[r].get(x);
    return z;
  }
  long long queryByOrder(long long x) {
    if (preQueryPos > size - 1)
      preQueryPos = size - 1;
    else {
      while (preQueryPos + 1 < size) {
        if (hull[preQueryPos].get(x) <= hull[preQueryPos + 1].get(x)) {
          preQueryPos++;
        } else
          break;
      }
    }
    return hull[preQueryPos].get(x);
  }
};
const int MN = 300155 * 4;
ConvexHull ch[MN];
vector<int> tr[MN];
bool isBuild[MN], del[300155];
void upt(int rt, int l, int r, int L, int R, int lid) {
  if (r <= L || R <= l) return;
  if (L <= l && r <= R) {
    tr[rt].push_back(lid);
    return;
  }
  int mid = (l + r) / 2;
  upt((rt << 1), l, mid, L, R, lid);
  upt((rt << 1 | 1), mid, r, L, R, lid);
}
void build(int rt) {
  if (isBuild[rt]) return;
  isBuild[rt] = 1;
  vector<pair<long long, long long>> vp;
  for (int id : tr[rt]) {
    assert(q[id].t == 1);
    vp.push_back({q[id].a, q[id].b});
  }
  sort(vp.begin(), vp.end());
  for (auto p : vp) ch[rt].add_line(p.first, p.second);
}
long long qy(int rt, int l, int r, int pos, long long x) {
  if (r < pos || pos <= l) return -(1LL << 60);
  build(rt);
  if (l + 1 == r) {
    return ch[rt].query(x);
  }
  int mid = (l + r) / 2;
  long long gg =
      max(qy((rt << 1), l, mid, pos, x), qy((rt << 1 | 1), mid, r, pos, x));
  gg = max(gg, ch[rt].query(x));
  return gg;
}
void fmain() {
  scanf("%d", &n);
  for (int(i) = 1; (i) <= (int)(n); (i)++) q[i].rd();
  for (int(i) = 1; (i) <= (int)(n); (i)++)
    if (q[i].t == 2) {
      upt(1, 0, n, q[i].id - 1, i, q[i].id);
      del[q[i].id] = 1;
    }
  for (int(i) = 1; (i) <= (int)(n); (i)++)
    if (q[i].t == 1 && !del[i]) {
      upt(1, 0, n, i - 1, n, i);
    }
  for (int(i) = 1; (i) <= (int)(n); (i)++)
    if (q[i].t == 3) {
      long long tmp = qy(1, 0, n, i, q[i].q);
      if (tmp == -(1LL << 60))
        puts("EMPTY SET");
      else
        printf("%lld\n", tmp);
    }
}
int main() {
  fmain();
  return 0;
}