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;
const int N = 1 << 19;
int n;
int C[N], x1[N], x2[N];
bool dead[N];
class line {
 public:
  int m, n;
  line() {}
  line(int m, int n) {
    this->m = m;
    this->n = n;
  }
  double intersect(line oth) { return (double)(n - oth.n) / (oth.m - m); }
  bool operator<(line oth) const {
    if (m != oth.m) return m < oth.m;
    return n < oth.n;
  }
};
bool kill(line a, line b) { return a.m == b.m and a.n > b.n; }
class convex {
 public:
  vector<line> ls, v;
  convex() {}
  void add(int m, int n) {
    while (v.size() >= 2) {
      line l1 = v[v.size() - 2];
      line l2 = v[v.size() - 1];
      line l3(m, n);
      if (kill(l3, l2) or l1.intersect(l3) <= l1.intersect(l2))
        v.pop_back();
      else
        break;
    }
    while (v.size() and kill({m, n}, v.back())) v.pop_back();
    v.push_back({m, n});
  }
  void init() {
    sort(ls.begin(), ls.end());
    for (auto l : ls) add(l.m, l.n);
  }
  void addLine(int m, int n) { ls.push_back({m, n}); }
  long long get(int x) {
    if (v.size() == 0) return -5e18;
    if (v.size() > 1 and v[v.size() - 2].intersect(v.back()) <= x)
      return (long long)v.back().m * x + v.back().n;
    int l = 0, r = (int)v.size() - 2;
    while (l < r) {
      int m = (l + r) >> 1;
      line l1 = v[m + 1];
      line l2 = v[m];
      if (l1.intersect(l2) >= x)
        r = m;
      else
        l = m + 1;
    }
    return (long long)v[l].m * x + v[l].n;
  }
} t[N << 1];
void up(int l, int r, int m, int n) {
  for (l += N, r += N; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
    if (l & 1) t[l].addLine(m, n);
    if (~r & 1) t[r].addLine(m, n);
  }
}
long long get(int x, int v) {
  long long res = -5e18;
  x += N;
  while (x >= 1) {
    res = max(res, t[x].get(v));
    x >>= 1;
  }
  return res;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", C + i);
    if (C[i] == 1) {
      scanf("%d %d", x1 + i, x2 + i);
    } else if (C[i] == 2) {
      scanf("%d", x1 + i);
      dead[x1[i]] = 1;
      up(x1[i], i - 1, x1[x1[i]], x2[x1[i]]);
    } else {
      scanf("%d", x1 + i);
    }
  }
  for (int i = 1; i <= n; i++)
    if (C[i] == 1 and !dead[i]) up(i, n, x1[i], x2[i]);
  for (int i = 1; i < (N << 1); i++) t[i].init();
  for (int i = 1; i <= n; i++) {
    if (C[i] == 3) {
      long long res = get(i, x1[i]);
      if (res < -4e18)
        puts("EMPTY SET");
      else
        printf("%lld\n", res);
    }
  }
  return 0;
}