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;
bool Q;
struct Line {
  mutable long long k, m, p;
  bool operator<(const Line &o) const { return Q ? p < o.p : k < o.k; }
};
struct HullDynamic : multiset<Line> {
  const long long inf = LLONG_MAX;
  long long div(long long a, long long b) {
    return a / b - ((a ^ b) < 0 && a % b);
  }
  bool isect(iterator x, iterator y) {
    if (y == end()) {
      x->p = inf;
      return false;
    }
    if (x->k == y->k)
      x->p = x->m > y->m ? inf : -inf;
    else
      x->p = div(y->m - x->m, x->k - y->k);
    return x->p >= y->p;
  }
  void add(long long k, long long m) {
    auto z = insert({k, m, 0}), y = z++, x = y;
    while (isect(y, z)) z = erase(z);
    if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
    while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
  }
  long long query(long long x) {
    assert(!empty());
    Q = 1;
    auto l = *lower_bound({0, 0, x});
    Q = 0;
    return l.k * x + l.m;
  }
};
struct Query {
  int in, out, type;
  long long a, b;
  long long ans;
  Query(int in, int out, int type, long long a, long long b,
        long long ans = -3e18)
      : in(in), out(out), type(type), a(a), b(b), ans(ans) {}
};
void solve(int l, int r, vector<Query> &query) {
  vector<Query> next;
  HullDynamic cht;
  bool flag = true;
  for (auto q : query) {
    if (q.in > r || q.out < l) continue;
    if (q.in <= l && q.out >= r && q.type == 0) {
      cht.add(q.a, q.b);
      continue;
    }
    if (q.type != 1) flag = false;
    next.push_back(q);
  }
  for (auto &q : next) {
    if (q.type == 1 && !cht.empty()) {
      q.ans = max(q.ans, cht.query(q.a));
    }
  }
  if (flag == true) {
    for (auto q : next) {
      if (q.ans == -3e18) {
        printf("EMPTY SET\n");
      } else {
        printf("%lld\n", q.ans);
      }
    }
    return;
  }
  if (next.empty()) return;
  int mid = (l + r) / 2;
  solve(l, mid, next);
  solve(mid + 1, r, next);
}
int32_t main() {
  int n;
  scanf("%d", &n);
  vector<int> out(n, 0);
  vector<pair<int, int>> aux(n);
  vector<Query> q;
  for (int t = 0; t < n; ++t) {
    int k;
    scanf("%d", &k);
    long long a, b;
    if (k == 1) {
      scanf("%lld %lld", &a, &b);
      aux[t] = {a, b};
      out[t] = -1;
    } else if (k == 2) {
      scanf("%lld", &a);
      a--;
      q.emplace_back(a, t, 0, aux[a].first, aux[a].second);
      out[a] = t;
    } else {
      scanf("%lld", &a);
      q.emplace_back(t, t, 1, a, 0, -3e18);
      out[t] = t;
    }
  }
  for (int i = 0; i < n; ++i) {
    if (out[i] == -1) {
      q.emplace_back(i, n, 0, aux[i].first, aux[i].second);
    }
  }
  solve(0, n, q);
  return 0;
}