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;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline int read() {
  int x = 0;
  char ch = getchar();
  bool positive = 1;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') positive = 0;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return positive ? x : -x;
}
inline void write(long long a) {
  if (a >= 10) write(a / 10);
  putchar('0' + a % 10);
}
inline void writeln(long long a) {
  if (a <= -4000000000000000000) {
    puts("EMPTY SET");
    return;
  }
  if (a < 0) {
    a = -a;
    putchar('-');
  }
  write(a);
  puts("");
}
const int N = 300005;
vector<pair<int, int> > v[N << 2];
pair<int, int> que[N], val[N];
priority_queue<pair<pair<int, int>, int> > qq;
int tong[N], n, pos[N], m, r[N], tot;
long long ans[N];
inline void insert(int l, int r, int i, int j, pair<int, int> k, int nod) {
  if (l == i && r == j) {
    v[nod].push_back(k);
    return;
  }
  int mid = (l + r) >> 1;
  if (j <= mid)
    insert(l, mid, i, j, k, nod << 1);
  else if (i > mid)
    insert(mid + 1, r, i, j, k, nod << 1 | 1);
  else {
    insert(l, mid, i, mid, k, nod << 1);
    insert(mid + 1, r, mid + 1, j, k, nod << 1 | 1);
  }
}
inline void build(int nod) {
  if (v[nod].size() <= 2) return;
  int top = 1;
  que[0] = v[nod][0];
  que[1] = v[nod][1];
  for (int i = 2; i < v[nod].size(); i++) {
    while (top && (long long)(que[top].second - que[top - 1].second) *
                          (v[nod][i].first - que[top].first) <=
                      (long long)(v[nod][i].second - que[top].second) *
                          (que[top].first - que[top - 1].first))
      top--;
    que[++top] = v[nod][i];
  }
  v[nod].resize(top + 1);
  for (int i = 0; i <= top; i++) v[nod][i] = que[i];
}
inline void build(int l, int r, int nod) {
  build(nod);
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(l, mid, nod << 1);
  build(mid + 1, r, nod << 1 | 1);
}
inline long long calc(pair<int, int> x, int xx) {
  return (long long)x.first * xx + x.second;
}
inline long long ask(int nod, int x) {
  int l = 0, r = v[nod].size() - 1;
  long long ans = -4e18;
  while (l <= r) {
    int len = (r - l) / 3, lmid = l + len, rmid = r - len;
    ans = max(ans, max(calc(v[nod][lmid], x), calc(v[nod][rmid], x)));
    if (calc(v[nod][lmid], x) < calc(v[nod][rmid], x))
      l = lmid + 1;
    else
      r = rmid - 1;
  }
  return ans;
}
inline long long ask(int l, int r, int pos, int q, int nod) {
  if (l == r) return ask(nod, q);
  int mid = (l + r) >> 1;
  if (pos <= mid)
    return max(ask(l, mid, pos, q, nod << 1), ask(nod, q));
  else
    return max(ask(mid + 1, r, pos, q, nod << 1 | 1), ask(nod, q));
}
struct data {
  int first, second, id;
} q[N];
inline bool cmp(data a, data b) { return a.first < b.first; }
int main() {
  n = read();
  for (int i = 1; i <= n; i++) {
    int op = read();
    if (op == 1) {
      int a = read(), b = read();
      val[pos[i] = ++m] = make_pair(a, b);
      tong[m] = 1;
    } else if (op == 2) {
      int t = pos[read()];
      r[t] = m++;
    } else {
      tot++;
      q[tot] = (data){m, read(), tot};
    }
  }
  for (int i = 1; i <= m; i++)
    if (tong[i]) {
      val[i].first = -val[i].first;
      qq.push(make_pair(val[i], i));
      val[i].first = -val[i].first;
    }
  while (!qq.empty()) {
    int id = qq.top().second;
    insert(1, m, id, r[id] ? r[id] : m, val[id], 1);
    qq.pop();
  }
  if (m) build(1, m, 1);
  sort(&q[1], &q[tot + 1], cmp);
  for (int i = 1; i <= tot; i++) {
    ans[q[i].id] =
        m ? (q[i].first ? ask(1, m, q[i].first, q[i].second, 1) : (-4e18))
          : -4e18;
  }
  for (int i = 1; i <= tot; i++) writeln(ans[i]);
}