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 bool upmin(T &x, T y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool upmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
const long double eps = 1e-11;
const long double pi = acos(-1);
const long long oo = 1 << 30;
const long long loo = 1ll << 60;
const long long mods = 998244353;
const long long MAXN = 300005;
const long long INF = 0x3f3f3f3f;
inline long long read() {
  long long f = 1, x = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = getchar();
  }
  return x * f;
}
vector<long long> Q[MAXN << 2], C[MAXN << 2];
long long m = 0, top = 0, cnt = 0, mx[MAXN << 2], c[MAXN], p[MAXN], id[MAXN];
pair<long long, long long> stk[MAXN << 2], a[MAXN], b[MAXN];
long long get(long long x, long long y) {
  if (!x) return -loo;
  return 1ll * a[x].first * y + a[x].second;
}
void update(long long x, long long l, long long r, long long y) {
  if (l > r) return;
  long long mid = (l + r) >> 1;
  if (get(mx[x], p[mid]) < get(y, p[mid]))
    stk[++top] = make_pair(x, mx[x]), swap(mx[x], y);
  if (get(mx[x], p[l]) < get(y, p[l])) update(x << 1, l, mid, y);
  if (get(mx[x], p[r]) < get(y, p[r])) update(x << 1 | 1, mid + 1, r, y);
}
long long query(long long x, long long l, long long r, long long y) {
  if (l == r) return get(mx[x], p[y]);
  long long mid = (l + r) >> 1;
  if (y <= mid)
    return max(get(mx[x], p[y]), query(x << 1, l, mid, y));
  else
    return max(get(mx[x], p[y]), query(x << 1 | 1, mid + 1, r, y));
}
void insert(long long x, long long l, long long r, long long L, long long R,
            long long y, long long z) {
  if (l >= L && r <= R) {
    if (z)
      Q[x].push_back(y);
    else
      C[x].push_back(y);
    return;
  }
  long long mid = (l + r) >> 1;
  if (R <= mid)
    insert(x << 1, l, mid, L, R, y, z);
  else if (L > mid)
    insert(x << 1 | 1, mid + 1, r, L, R, y, z);
  else
    insert(x << 1, l, mid, L, mid, y, z),
        insert(x << 1 | 1, mid + 1, r, mid + 1, R, y, z);
}
void solve(long long x, long long l, long long r) {
  long long mid = (l + r) >> 1, lst = top;
  for (auto v : C[x]) update(1, 1, c[cnt], v);
  if (l == r) {
    for (auto v : Q[x]) {
      long long t = query(1, 1, c[cnt], v);
      if (t <= -loo)
        puts("EMPTY SET");
      else
        printf("%lld\n", t);
    }
    return;
  }
  solve(x << 1, l, mid);
  solve(x << 1 | 1, mid + 1, r);
  while (top > lst) mx[stk[top].first] = stk[top].second, top--;
}
signed main() {
  long long n = read(), num = 0;
  for (long long i = 1; i <= n; i++) {
    long long opt = read(), x, y;
    if (opt == 1)
      x = read(), y = read(), a[++num] = make_pair(x, y), id[i] = num;
    else if (opt == 2)
      x = read(), insert(1, 1, n, x, i - 1, id[x], 0), id[x] = -1;
    else
      x = read(), b[++cnt] = make_pair(x, i);
  }
  for (long long i = 1; i <= n; i++)
    if (id[i] > 0) insert(1, 1, n, i, n, id[i], 0);
  sort(b + 1, b + cnt + 1,
       [&](pair<long long, long long> x, pair<long long, long long> y) {
         return x.first < y.first;
       });
  b[0].first = -INF;
  for (long long i = 1; i <= cnt; i++)
    c[i] = c[i - 1] + (b[i].first != b[i - 1].first);
  for (long long i = 1; i <= cnt; i++)
    p[c[i]] = b[i].first, insert(1, 1, n, b[i].second, b[i].second, c[i], 1);
  solve(1, 1, n);
  return 0;
}