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;
int q, OP[300010][2];
int fin[300010];
struct Line {
  int k, b;
  double xLeft;
  bool type;
  Line() {
    xLeft = -9e18;
    type = false;
  }
  bool operator<(const Line &l) const {
    if (l.type) return xLeft < l.xLeft;
    return k < l.k || k == l.k && b < l.b;
  }
} lines[300010];
double intersect(const Line &a, const Line &b) {
  return 1.0 * (b.b - a.b) / (a.k - b.k);
}
struct Envelope {
  set<Line> env;
  Envelope() { env.clear(); }
  bool hasNext(set<Line>::iterator it) { return next(it) != env.end(); }
  bool irrelevant(const Line &a, const Line &b, const Line &c) {
    if (a.k == b.k) return true;
    return intersect(a, b) <= intersect(a, c);
  }
  bool check(set<Line>::iterator it) {
    if (it == env.begin() || prev(it) == env.begin()) return false;
    return irrelevant(*it, *prev(it), *prev(prev(it)));
  }
  void addLine(Line l) {
    Line t;
    auto it = env.insert(l).first;
    if (hasNext(it) && check(next(it))) {
      env.erase(it);
      return;
    }
    while (check(it)) env.erase(prev(it));
    if (it != env.begin()) {
      t = *it;
      t.xLeft = intersect(*it, *prev(it));
      env.erase(it);
      it = env.insert(t).first;
    }
    while (hasNext(it) && hasNext(next(it)) && check(next(next(it))))
      env.erase(next(it));
    if (next(it) != env.end()) {
      t = *next(it);
      t.xLeft = intersect(*it, *next(it));
      env.erase(next(it));
      env.insert(t);
    }
  }
  long long calcLine(int x) {
    Line goal;
    goal.type = true;
    goal.xLeft = x;
    if (env.empty()) return -9e18;
    auto it = prev(env.lower_bound(goal));
    return 1LL * (it->k) * x + (it->b);
  }
};
struct SegmentTree {
  int tl, tr;
  Line tv;
  Envelope env[1200010];
  void add(int id, int l, int r) {
    int nxt = id << 1, mid = (l + r) >> 1;
    if (tl <= l && r <= tr)
      env[id].addLine(tv);
    else {
      if (tl <= mid) add(nxt, l, mid);
      if (tr > mid) add(nxt | 1, mid + 1, r);
    }
  }
  long long query(int id, int l, int r) {
    int nxt = id << 1, mid = (l + r) >> 1;
    if (l == r) return env[id].calcLine(OP[tl][1]);
    return max(env[id].calcLine(OP[tl][1]),
               tl <= mid ? query(nxt, l, mid) : query(nxt | 1, mid + 1, r));
  }
  void insert(int l, int r, const Line &v) {
    tl = l;
    tr = r;
    tv = v;
    add(1, 1, q);
  }
  long long query(int pos) {
    tl = tr = pos;
    return query(1, 1, q);
  }
} tree;
int main() {
  int i;
  long long val;
  scanf("%d", &q);
  for (i = 1; i <= q; i++) fin[i] = q;
  for (i = 1; i <= q; i++) {
    scanf("%d", &OP[i][0]);
    if (OP[i][0] == 1)
      scanf("%d%d", &lines[i].k, &lines[i].b);
    else {
      scanf("%d", &OP[i][1]);
      if (OP[i][0] == 2) fin[OP[i][1]] = i;
    }
  }
  for (i = 1; i <= q; i++) {
    if (OP[i][0] == 1)
      tree.insert(i, fin[i], lines[i]);
    else if (OP[i][0] == 3) {
      val = tree.query(i);
      if (val <= -9e18)
        printf("EMPTY SET\n");
      else
        printf("%I64d\n", val);
    }
  }
}