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;
long double safe_sqrt(long double x) { return sqrt(max((long double)0.0, x)); }
long long GI(long long& x) { return scanf("%lld", &x); }
const long long INF = 1000111000111000111LL;
const long long MN = 300111;
struct Line {
  long long a, b;
  long long from, to;
} lines[MN];
struct Hull {
  vector<long double> x;
  vector<long long> a;
  vector<long long> b;
  void init() {
    x.clear();
    a.clear();
    b.clear();
  }
  void remove() {
    a.pop_back();
    b.pop_back();
    x.pop_back();
  }
  void insert(Line l) {
    if (a.empty()) {
      x.push_back(-INF);
      a.push_back(l.a);
      b.push_back(l.b);
    } else {
      long double xNew = -INF;
      while (!a.empty()) {
        if (a.back() == l.a) {
          b.back() = max(b.back(), l.b);
          return;
        }
        assert(l.a > a.back());
        xNew = 1.0 * (b.back() - l.b) / (l.a - a.back());
        if (xNew < x.back()) {
          remove();
        } else
          break;
      }
      a.push_back(l.a);
      b.push_back(l.b);
      x.push_back(xNew);
    }
  }
  long long get(long long x0) {
    if (a.empty()) {
      return -INF;
    }
    long long i = upper_bound(x.begin(), x.end(), x0) - x.begin() - 1;
    return a[i] * x0 + b[i];
  }
};
Hull it[MN * 4];
void init(long long i, long long l, long long r) {
  it[i].init();
  if (l == r) return;
  long long mid = (l + r) >> 1;
  init(i << 1, l, mid);
  init(i << 1 | 1, mid + 1, r);
}
void update(long long i, long long l, long long r, long long u, long long v,
            Line t) {
  if (v < l || r < u) return;
  if (u <= l && r <= v) {
    it[i].insert(t);
    return;
  }
  long long mid = (l + r) >> 1;
  update(i << 1, l, mid, u, v, t);
  update(i << 1 | 1, mid + 1, r, u, v, t);
}
long long get(long long i, long long l, long long r, long long time,
              long long x0) {
  if (time < l || r < time) return -INF;
  long long res = it[i].get(x0);
  if (l == r) return res;
  long long mid = (l + r) >> 1;
  res = max(res, get(i << 1, l, mid, time, x0));
  res = max(res, get(i << 1 | 1, mid + 1, r, time, x0));
  return res;
}
bool operator<(const Line& u, const Line& v) {
  if (u.a != v.a) return u.a < v.a;
  return u.b > v.b;
}
long long nLine, id[MN];
struct Query {
  long long time, x0;
} queries[MN];
long long nQuery;
int main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout << (fixed) << setprecision(9);
  long long q;
  while (GI(q) == 1) {
    nLine = 0;
    nQuery = 0;
    for (long long i = (1), _b = (q); i <= _b; ++i) {
      long long typ;
      GI(typ);
      if (typ == 1) {
        ++nLine;
        lines[nLine].from = i;
        lines[nLine].to = q;
        GI(lines[nLine].a);
        GI(lines[nLine].b);
        id[i] = nLine;
      } else if (typ == 2) {
        long long x;
        GI(x);
        long long lineId = id[x];
        lines[lineId].to = i;
      } else {
        ++nQuery;
        queries[nQuery].time = i;
        GI(queries[nQuery].x0);
      }
    }
    sort(lines + 1, lines + nLine + 1);
    init(1, 1, q);
    for (long long i = (1), _b = (nLine); i <= _b; ++i) {
      update(1, 1, q, lines[i].from, lines[i].to, lines[i]);
    }
    for (long long i = (1), _b = (nQuery); i <= _b; ++i) {
      auto t = get(1, 1, q, queries[i].time, queries[i].x0);
      if (t == -INF)
        puts("EMPTY SET");
      else
        printf("%lld\n", t);
    }
  }
}