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;
struct lichao {
  int l, r;
  long long A, B;
  lichao() : l(0), r(0), A(0), B(-0x7fffffffffffffffLL) {}
} tree[3 << 20];
const int MAX = 1e9, SZ = 1 << 19, MAX_SIZE = 1 << 20;
int op, node_cnt = 2 * SZ, T[300000];
vector<pair<int, int>> query;
char buf[MAX_SIZE], obuf[MAX_SIZE];
inline char get_char() {
  static int p = 0, s = 0;
  if (p == s) {
    p = 0;
    s = fread(buf, 1, MAX_SIZE, stdin);
    if (p == s) return 0;
  }
  return buf[p++];
}
inline int get_int() {
  int ret = 0;
  bool is_negative = false;
  char c = -1;
  while (!('0' <= c && c <= '9') && c != '-') c = get_char();
  if (c == '-') {
    is_negative = true;
    c = get_char();
  }
  while ('0' <= c && c <= '9') ret *= 10, ret += c - '0', c = get_char();
  return (is_negative ? -ret : ret);
}
inline void flush_output() {
  if (op) {
    fwrite(obuf, 1, op, stdout);
    op = 0;
  }
}
inline void put_char(char c) {
  if (op == MAX_SIZE) {
    flush_output();
  }
  obuf[op++] = c;
}
inline void print_int(long long n) {
  static char temp[30];
  bool is_negative = (n < 0);
  int c = 29;
  if (n == 0) {
    put_char('0');
  } else {
    for (n = abs(n); n; n /= 10) {
      temp[c--] = n % 10 + '0';
    }
    if (is_negative) {
      put_char('-');
    }
    for (c++; c < 30; c++) {
      put_char(temp[c]);
    }
  }
  put_char('\n');
}
int get_sign(long long a) { return a < 0 ? -1 : a > 0; }
void add_line2(long long A, long long B, int p) {
  int s = -MAX, e = MAX;
  for (;;) {
    int m = (s + e) / 2;
    long long ys = A * s + B, ym = A * m + B, ye = A * e + B, &pA = tree[p].A,
              &pB = tree[p].B;
    long long pys = pA * s + pB, pym = pA * m + pB, pye = pA * e + pB;
    if (ym > pym) {
      swap(A, pA);
      swap(B, pB);
      swap(ys, pys);
      swap(ym, pym);
      swap(ye, pye);
    }
    if (pys >= ys && pye >= ye) return;
    if (get_sign(ys - pys) * get_sign(ym - pym) < 0 || ym == pym && ys > pys) {
      if (tree[p].l == 0) tree[p].l = node_cnt++;
      p = tree[p].l;
      e = m;
    } else {
      if (tree[p].r == 0) tree[p].r = node_cnt++;
      p = tree[p].r;
      s = m + 1;
    }
  }
}
void add_line(int s, int e, long long A, long long B) {
  for (s += SZ, e += SZ; s <= e; s >>= 1, e >>= 1) {
    if (s & 1) add_line2(A, B, s++);
    if (~e & 1) add_line2(A, B, e--);
  }
}
long long get_maxy2(int x, int p) {
  long long ret = -0x7fffffffffffffffLL;
  int s = -MAX, e = MAX;
  while (p && s < e) {
    int m = (s + e) / 2;
    ret = max(ret, tree[p].A * x + tree[p].B);
    if (x <= m) {
      p = tree[p].l;
      e = m;
    } else {
      p = tree[p].r;
      s = m + 1;
    }
  }
  return max(ret, tree[p].A * x + tree[p].B);
}
long long get_maxy(int t, int x) {
  long long ret;
  for (ret = get_maxy2(x, t += SZ); t >>= 1;) ret = max(ret, get_maxy2(x, t));
  return ret;
}
int main() {
  int Q = get_int();
  long long a, b;
  memset(T, -1, sizeof(T));
  query.resize(Q);
  for (int i = 0; i < Q; i++) {
    int t = get_int();
    a = get_int();
    if (t == 1) {
      query[i] = {a, get_int()};
      T[i] = Q - 1;
    } else if (t == 2) {
      T[--a] = i;
      T[i] = -2;
    } else
      query[i].first = a;
  }
  for (int i = 0; i < Q; i++) {
    tie(a, b) = query[i];
    if (T[i] == -1) {
      if ((b = get_maxy(i, a)) == -0x7fffffffffffffffLL) {
        put_char('E');
        put_char('M');
        put_char('P');
        put_char('T');
        put_char('Y');
        put_char(' ');
        put_char('S');
        put_char('E');
        put_char('T');
        put_char('\n');
      } else
        print_int(b);
    } else if (T[i] >= i)
      add_line(i, T[i], a, b);
  }
  flush_output();
  return 0;
}