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 void read(T &t) {
  t = 0;
  char c = getchar();
  long long f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -f;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    t = (t << 3) + (t << 1) + c - '0';
    c = getchar();
  }
  t *= f;
}
template <typename T, typename... Args>
inline void read(T &t, Args &...args) {
  read(t);
  read(args...);
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    x = -x;
    putchar('-');
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
struct Node {
  long long x, y;
  long long f(long long k) { return x * k + y; }
  bool operator<(const Node &p) const { return x != p.x ? x < p.x : y < p.y; }
};
long long n, cnt;
long long q[300010][3], opt[300010][3];
vector<Node> Tree[300010 << 1];
void update(long long l, long long r, long long tl, long long tr, Node oo) {
  long long p = (l + r) | (l != r);
  if (l >= tl && r <= tr) return Tree[p].push_back(oo);
  long long mid = (l + r) >> 1;
  if (tl <= mid) update(l, mid, tl, tr, oo);
  if (tr > mid) update(mid + 1, r, tl, tr, oo);
}
bool check(vector<Node> &t, long long i, long long j, long long k) {
  return ((t[i].y - t[j].y) * (t[k].x - t[i].x) >=
          (t[i].y - t[k].y) * (t[j].x - t[i].x));
}
void maintain(vector<Node> &t) {
  static long long S[300010], size;
  vector<Node> tmp;
  sort(t.begin(), t.end());
  size = 0;
  for (register long long i = 0; i < t.size(); ++i) {
    while ((size && t[S[size]].x == t[i].x) ||
           (size > 1 && check(t, S[size - 1], S[size], i)))
      size--;
    S[++size] = i;
  }
  for (register long long i = 1; i <= size; ++i) tmp.push_back(t[S[i]]);
  t = tmp;
}
long long get(long long k, long long id) {
  if (!Tree[id].size()) return -2e18;
  long long l = 0, r = Tree[id].size() - 1;
  while (l < r) {
    long long mid = (l + r) >> 1;
    if (Tree[id][mid].f(k) > Tree[id][mid + 1].f(k))
      r = mid;
    else
      l = mid + 1;
  }
  return Tree[id][l].f(k);
}
long long calc(long long l, long long r, long long k, long long pos) {
  long long res = -2e18;
  while (l < r) {
    long long p = (l + r) | (l != r), mid = (l + r) >> 1;
    res = max(res, get(k, p));
    if (pos <= mid)
      r = mid;
    else
      l = mid + 1;
  }
  return res = max(res, get(k, (l + r) | (l != r)));
}
signed main() {
  read(n);
  for (register long long i = 1, op; i <= n; ++i) {
    read(op, opt[i][1]);
    if (op == 1)
      read(opt[i][2]);
    else if (op == 2) {
      long long x = opt[i][1];
      update(1, n, x, i, Node{opt[x][1], opt[x][2]});
      opt[x][1] = opt[i][1] = 2e18;
    } else {
      q[++cnt][1] = opt[i][1];
      q[cnt][2] = i, opt[i][1] = 2e18;
    }
  }
  for (register long long i = 1; i <= n; ++i)
    if (opt[i][1] != 2e18) update(1, n, i, n, Node{opt[i][1], opt[i][2]});
  for (register long long i = 1; i <= (n << 1); ++i)
    if (Tree[i].size()) maintain(Tree[i]);
  for (register long long i = 1; i <= cnt; ++i) {
    long long res = calc(1, n, q[i][1], q[i][2]);
    if (res == -2e18)
      puts("EMPTY SET");
    else
      write(res), putchar('\n');
  }
  return 0;
}