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