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;
template <typename T>
inline T read(T& x) {
  x = 0;
  int f = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x = f ? -x : x;
}
const int N = 3e5 + 10;
const int DEL = 1e9 + 7;
const long long INF = 2000000000000000000LL;
struct Line {
  int k, b;
  Line() {}
  Line(int k, int b) : k(k), b(b) {}
  bool operator<(const Line& rhs) const {
    return k ^ rhs.k ? k < rhs.k : b < rhs.b;
  }
  long long f(int x) { return (long long)k * x + b; }
};
vector<Line> T[N << 2];
pair<int, int> seg[N], op[N];
int n, t, c, i, cnt, S[N];
long long res;
void add(int root, int l, int r, int L, int R, Line a) {
  if (L <= l && r <= R) {
    T[root].push_back(a);
    return;
  }
  int mid = l + ((r - l) >> 1);
  if (L <= mid) add(root << 1, l, mid, L, R, a);
  if (mid < R) add(root << 1 | 1, mid + 1, r, L, R, a);
}
bool check(vector<Line>& v, int i, int j, int k) {
  return (long long)(v[i].b - v[j].b) * (v[k].k - v[i].k) >=
         (long long)(v[i].b - v[k].b) * (v[j].k - v[i].k);
}
void calc(vector<Line>& T) {
  int i, t;
  sort(T.begin(), T.end());
  for (i = 0, t = 0; i < (int)T.size(); ++i) {
    while ((t && T[S[t]].k == T[i].k) || (t > 1 && check(T, S[t - 1], S[t], i)))
      t--;
    S[++t] = i;
  }
  vector<Line> nxt;
  for (i = 1; i <= t; i++) nxt.push_back(T[S[i]]);
  T = nxt;
}
long long get(int x, int root) {
  if (!T[root].size()) return -INF;
  int l = 0, r = (int)T[root].size() - 2, res = 0;
  while (l <= r) {
    int mid = l + ((r - l) >> 1);
    if (T[root][mid].f(x) <= T[root][mid + 1].f(x)) {
      l = mid + 1;
      res = mid + 1;
    } else
      r = mid - 1;
  }
  return T[root][res].f(x);
}
void query(int root, int l, int r, int pos, int x) {
  res = max(res, get(x, root));
  if (l == r) return;
  int mid = l + ((r - l) >> 1);
  if (pos <= mid)
    query(root << 1, l, mid, pos, x);
  else
    query(root << 1 | 1, mid + 1, r, pos, x);
}
int main() {
  read(n);
  for (i = 1; i <= n; ++i) {
    read(c), read(seg[i].first);
    if (c == 1)
      read(seg[i].second);
    else if (c == 2) {
      int x = seg[i].first;
      add(1, 1, n, x, i, Line(seg[x].first, seg[x].second));
      seg[x].first = seg[i].first = DEL;
    } else
      op[++cnt] = make_pair(seg[i].first, i), seg[i].first = DEL;
  }
  for (i = 1; i <= n; ++i)
    if (seg[i].first != DEL) {
      add(1, 1, n, i, n, Line(seg[i].first, seg[i].second));
    }
  for (i = 1; i <= (n << 1); ++i)
    if (T[i].size()) calc(T[i]);
  for (i = 1; i <= cnt; ++i) {
    res = -INF;
    query(1, 1, n, op[i].second, op[i].first);
    if (res == -INF)
      puts("EMPTY SET");
    else
      printf("%lld\n", res);
  }
  return 0;
}