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 = 3e5 + 5;
const long long MN = numeric_limits<long long>::min();
template <typename T>
struct convex_hull {
  vector<pair<T, T> > cvh;
  void pushBack(pair<T, T> a) {
    while (cvh.size() > 1) {
      pair<T, T> &b = cvh[cvh.size() - 1];
      pair<T, T> &c = cvh[cvh.size() - 2];
      if ((c.second - a.second) * (b.first - c.first) <=
          (c.second - b.second) * (a.first - c.first))
        cvh.pop_back();
      else
        break;
    }
    cvh.push_back(a);
  }
  T getY(T x, T k, T b) { return k * x + b; }
  T getY(T x) {
    T mx = numeric_limits<T>::min();
    int l = 0, r = cvh.size() - 1;
    while (l <= r) {
      int m1 = l + (r - l) / 3;
      int m2 = r - (r - l) / 3;
      T r1 = getY(x, cvh[m1].first, cvh[m1].second);
      T r2 = getY(x, cvh[m2].first, cvh[m2].second);
      mx = max(mx, max(r1, r2));
      if (r1 < r2)
        l = m1 + 1;
      else
        r = m2 - 1;
    }
    return mx;
  }
};
vector<vector<int> > v;
vector<convex_hull<long long> > c;
int f[N];
int k[N], b[N];
int n;
void add(int l, int r, int w) {
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) v[l++].push_back(w);
    if (r & 1) v[--r].push_back(w);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  int m;
  cin >> m;
  n = m + 1;
  v.resize(n << 1);
  c.resize(n << 1);
  vector<pair<int, int> > qq;
  for (int i = 1; i <= m; i++) {
    int t;
    cin >> t;
    int q;
    switch (t) {
      case 1:
        cin >> k[i] >> b[i];
        f[i] = 1;
        break;
      case 2:
        cin >> q;
        f[q] = 2;
        add(q, i, q);
        break;
      case 3:
        cin >> q;
        qq.push_back(make_pair(i, q));
        break;
    }
  }
  for (int i = 1; i <= m; i++)
    if (f[i] == 1) add(i, n, i);
  for (int i = 1; i < v.size(); i++) {
    if (v[i].empty()) continue;
    vector<pair<long long, long long> > e;
    for (auto j : v[i]) e.push_back(make_pair(k[j], b[j]));
    sort(e.begin(), e.end());
    for (auto &it : e) c[i].pushBack(it);
  }
  for (auto &it : qq) {
    long long ans = MN;
    int i = it.first + n;
    int x = it.second;
    while (i) {
      ans = max(ans, c[i].getY(x));
      i >>= 1;
    }
    if (ans == MN) {
      cout << "EMPTY SET" << endl;
      continue;
    }
    cout << ans << endl;
  }
  return 0;
}