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 B = 1000;
const long long NIL = LLONG_MIN;
struct P {
  long long x, y;
  P() : x(0), y(0) {}
  P(long long x, long long y) : x(x), y(y) {}
  P operator-() const { return P(-x, -y); }
  P operator-(const P &r) const { return P(x - r.x, y - r.y); }
  bool operator<(const P &r) const { return x != r.x ? x < r.x : y < r.y; }
};
long long cross(P a, P b) { return a.x * b.y - a.y * b.x; }
vector<P> upper_hull(vector<P> &ps) {
  if (ps.size() <= 1) return ps;
  vector<P> a(ps.size());
  int s = 0;
  for (auto p : ps) {
    if (p.x == NIL) continue;
    while (s >= 2 && cross(a[s - 2] - a[s - 1], p - a[s - 1]) <= 0) s--;
    a[s++] = p;
  }
  a.resize(s);
  return a;
}
long long maximum(vector<P> &hull, long long q) {
  if (hull.empty()) return NIL;
  long long pass = hull.size() - 1;
  long long fail = -1;
  while (pass - fail > 1) {
    long long mid = (pass + fail) / 2;
    if (hull[mid].x * q + hull[mid].y > hull[mid + 1].x * q + hull[mid + 1].y) {
      pass = mid;
    } else {
      fail = mid;
    }
  }
  return hull[pass].x * q + hull[pass].y;
}
int main() {
  int n;
  cin >> n;
  vector<long long> t(n), x(n), y(n);
  vector<pair<P, int>> ps(n, make_pair(P(NIL, NIL), -1));
  for (int i = 0; i < n; i++) {
    scanf("%lld", &t[i]);
    ps[i].second = i;
    if (t[i] == 1) {
      scanf("%lld %lld", &x[i], &y[i]);
      ps[i] = make_pair(P(x[i], y[i]), i);
    } else if (t[i] == 2) {
      scanf("%lld", &x[i]);
      x[i]--;
    } else {
      scanf("%lld", &x[i]);
    }
  }
  vector<bool> actived(n);
  vector<int> curr;
  vector<P> prev;
  for (int i = 0; i < n; i += B) {
    curr.clear();
    prev.clear();
    int R = min(n, i + B);
    bitset<303030> bucket;
    for (int j = i; j < R; j++) {
      if (t[j] == 1) {
        bucket[j] = true;
      } else if (t[j] == 2) {
        bucket[x[j]] = true;
      }
    }
    for (auto p : ps) {
      int j = p.second;
      if (j >= R) break;
      if (t[j] == 1 && actived[j]) {
        if (bucket[j]) {
          curr.push_back(j);
        } else {
          prev.emplace_back(p.first);
        }
      }
    }
    auto prev_upper = upper_hull(prev);
    for (int j = i; j < R; j++) {
      if (t[j] == 1) {
        curr.push_back(j);
        actived[j] = true;
      } else if (t[j] == 2) {
        actived[x[j]] = false;
      } else {
        long long mx = NIL;
        mx = max(mx, maximum(prev_upper, x[j]));
        for (int l = 0; l < curr.size(); l++) {
          int id = curr[l];
          if (actived[id]) {
            mx = max(mx, x[id] * x[j] + y[id]);
          }
        }
        if (mx == NIL) {
          puts("EMPTY SET");
        } else {
          printf("%lld\n", mx);
        }
      }
    }
    sort(ps.begin() + i, ps.begin() + R);
    inplace_merge(ps.begin(), ps.begin() + i, ps.begin() + R);
  }
}