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;
inline int Read() {
  char ch = getchar();
  while (!((ch >= '0' && ch <= '9') || ch == '-')) ch = getchar();
  int x = 0, p = 1;
  if (ch == '-') p = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * p;
}
struct cht {
  struct Line {
    int a;
    long long b;
    long long val;
    double xLeft;
    bool type;
    Line(long long _a = 0, long long _b = 0) {
      a = _a;
      b = _b;
      xLeft = -2 * (1e18);
      type = 0;
      val = 0;
    }
    long long valueAt(int x) const { return 1LL * a * x + b; }
    friend bool areParallel(const Line &l1, const Line &l2) {
      return l1.a == l2.a;
    }
    friend double intersectX(const Line &l1, const Line &l2) {
      return areParallel(l1, l2) ? 2 * (1e18)
                                 : 1.0 * (l2.b - l1.b) / (l1.a - l2.a);
    }
    bool operator<(const Line &l2) const {
      if (!l2.type) return a < l2.a;
      return xLeft > l2.val;
    }
  };
  set<Line> hull;
  void init() { hull.clear(); }
  bool hasPrev(set<Line>::iterator it) { return it != hull.begin(); }
  bool hasNext(set<Line>::iterator it) {
    return it != hull.end() && next(it) != hull.end();
  }
  bool irrelevant(const Line &l1, const Line &l2, const Line &l3) {
    return intersectX(l1, l3) <= intersectX(l1, l2);
  }
  bool irrelevant(set<Line>::iterator it) {
    return hasPrev(it) && hasNext(it) &&
           (irrelevant(*next(it), *it, *prev(it)));
  }
  set<Line>::iterator updateLeftBorder(set<Line>::iterator it) {
    if (!hasNext(it)) {
      return it;
    }
    double val = intersectX(*it, *next(it));
    Line buf(*it);
    it = hull.erase(it);
    buf.xLeft = val;
    it = hull.insert(it, buf);
    return it;
  }
  void addLine(int a, long long b) {
    Line l3 = Line(a, b);
    auto it = hull.lower_bound(l3);
    if (it != hull.end() && areParallel(*it, l3)) {
      if (it->b > b) {
        it = hull.erase(it);
      } else {
        return;
      }
    }
    it = hull.insert(it, l3);
    if (irrelevant(it)) {
      hull.erase(it);
      return;
    }
    while (hasPrev(it) && irrelevant(prev(it))) {
      hull.erase(prev(it));
    }
    while (hasNext(it) && irrelevant(next(it))) {
      hull.erase(next(it));
    }
    it = updateLeftBorder(it);
    if (hasPrev(it)) {
      updateLeftBorder(prev(it));
    }
    if (hasNext(it)) {
      updateLeftBorder(next(it));
    }
  }
  long long getBest(int x) {
    Line q;
    q.val = x;
    q.type = 1;
    auto bestLine = hull.lower_bound(q);
    if (bestLine == hull.end()) {
      return 2 * (1e18);
    }
    return bestLine->valueAt(x);
  }
} segTree[300005 << 2];
int TYPE[300005];
pair<int, int> ins[300005];
int qury[300005];
int deadline[300005];
void update(int t, int i, int j, const int &ri, const int &rj, const int &idx) {
  if (ri <= i && j <= rj) {
    segTree[t].addLine(-ins[idx].first, -ins[idx].second);
    return;
  }
  int left = t << 1, right = left | 1, mid = (i + j) >> 1;
  if (ri <= mid) update(left, i, mid, ri, rj, idx);
  if (rj > mid) update(right, mid + 1, j, ri, rj, idx);
}
long long query(int t, int i, int j, const int &idx, long long ans) {
  if (i == j) return max(ans, -segTree[t].getBest(qury[idx]));
  int left = t << 1, right = left | 1, mid = (i + j) >> 1;
  if (idx <= mid)
    return query(left, i, mid, idx, max(ans, -segTree[t].getBest(qury[idx])));
  return query(right, mid + 1, j, idx,
               max(ans, -segTree[t].getBest(qury[idx])));
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) deadline[i] = n;
  for (int i = 1; i <= n; i++) {
    int t;
    t = Read();
    TYPE[i] = t;
    if (t == 1) {
      int a, b;
      a = Read();
      b = Read();
      ins[i] = make_pair(a, b);
    } else if (t == 2) {
      int x;
      x = Read();
      deadline[x] = i;
    } else if (t == 3) {
      int q;
      q = Read();
      qury[i] = q;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (TYPE[i] == 2) continue;
    if (TYPE[i] == 1)
      update(1, 1, n, i, deadline[i], i);
    else {
      long long x = query(1, 1, n, i, -3 * (1e18));
      if (x == -2 * (1e18))
        printf("EMPTY SET\n");
      else
        printf("%lld\n", x);
    }
  }
}