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;
using ll = long long;
const int N = 3e5 + 66;
const ll inf = 2e18;
struct node {
  int L, R;
  ll x, y;
  node(int a, int b, ll c, ll d) { L = a, R = b, x = c, y = d; }
};
vector<node> lines;
ll a[N], b[N], ans[N], q[N];
int t[N], rem[N], ind[N];
struct line {
  ll k, b;
  ll f(ll x) { return k * x + b; }
  line(ll a, ll c) { k = a, b = c; }
};
using ld = long double;
ld inter(line a, line b) { return (ld)(b.b - a.b) / (ld)(a.k - b.k); }
struct CHT {
  vector<line> v;
  CHT() { v.assign(N, {0, 0}); }
  int sz = 0, l = 0;
  void clear() { sz = l = 0; }
  void add(line a) {
    if (sz > 0 && v[sz - 1].k == a.k) {
      if (v[sz - 1].b < a.b)
        sz--;
      else
        return;
    }
    while (sz >= 2 && inter(v[sz - 1], v[sz - 2]) > inter(v[sz - 2], a)) sz--;
    v[sz++] = a;
  }
  ll get(ll x) {
    if (sz == l) return -inf;
    while (sz > l + 1 && inter(v[l], v[1 + l]) < ld(x)) ++l;
    return v[l].f(x);
  }
};
const int K = 600;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> t[i];
    if (t[i] == 1) cin >> a[i] >> b[i];
    if (t[i] == 2) {
      cin >> ind[i];
      ind[i]--;
      rem[ind[i]] = i;
      int L = ind[i], R = i;
      ll x = a[ind[i]], y = b[ind[i]];
      lines.emplace_back(L, R, x, y);
    }
    if (t[i] == 3) cin >> q[i], ans[i] = -inf;
  }
  for (int i = 0; i < n; ++i) {
    if (t[i] == 1 && rem[i] == 0) {
      rem[i] = n;
      lines.emplace_back(i, n, a[i], b[i]);
    }
  }
  CHT cht;
  sort(lines.begin(), lines.end(),
       [](node a, node b) { return a.x != b.x ? a.x < b.x : a.y < b.y; });
  vector<int> ask;
  vector<int> ins;
  for (int L = 0; L < n; L += K) {
    int R = L + K;
    R = min(R, n);
    cht.clear();
    for (auto line : lines) {
      if (line.L < L && line.R >= R) {
        cht.add({line.x, line.y});
      }
    }
    ask.clear();
    ins.clear();
    for (int i = L; i < R; ++i) {
      if (t[i] == 1) {
        ins.emplace_back(i);
      } else if (t[i] == 3) {
        ask.emplace_back(i);
        for (int j : ins) {
          if (rem[j] > i) {
            ans[i] = max(ans[i], a[j] * q[i] + b[j]);
          }
        }
      }
    }
    ins.clear();
    for (int i = R - 1; i >= L; --i) {
      if (t[i] == 2) {
        ins.emplace_back(i);
      } else if (t[i] == 3) {
        for (int j : ins) {
          if (ind[j] < i) {
            ans[i] = max(ans[i], a[ind[j]] * q[i] + b[ind[j]]);
          }
        }
      }
    }
    sort(ask.begin(), ask.end(), [](int a, int b) { return q[a] < q[b]; });
    for (int i : ask) {
      ans[i] = max(ans[i], cht.get(q[i]));
    }
  }
  for (int i = 0; i < n; ++i) {
    if (t[i] == 3) {
      if (ans[i] == -inf)
        cout << "EMPTY SET\n";
      else
        cout << ans[i] << "\n";
    }
  }
}