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 = 1e5 + 20;
const long long oo = 1e13 + 20;
const int MOD = 1e9 + 7;
struct line {
  long long m, b;
  long long eval(long long x) { return m * x + b; }
};
struct cht {
  vector<line> lines;
  vector<double> inter;
  int n, i;
  double get_inter(line &a, line &b) { return double(b.b - a.b) / (a.m - b.m); }
  inline bool ok(line &a, line &b, line &c) {
    return double(a.b - c.b) / (c.m - a.m) > double(a.b - b.b) / (b.m - a.m);
  }
  void add(line l) {
    n = lines.size();
    if (n && lines.back().m == l.m && lines.back().b >= l.b) return;
    if (n == 1 && lines.back().m == l.m && lines.back().b < l.b)
      lines.pop_back(), n--;
    while (n >= 2 && !ok(lines[n - 2], lines[n - 1], l)) {
      n--;
      lines.pop_back();
      inter.pop_back();
    }
    lines.push_back(l);
    n++;
    if (n >= 2) inter.push_back(get_inter(lines[n - 1], lines[n - 2]));
  }
  long long get_max(double x) {
    if (lines.size() == 0) return LLONG_MIN;
    if (lines.size() == 1) return lines[0].eval(x);
    int pos = lower_bound(inter.begin(), inter.end(), x) - inter.begin();
    return lines[pos].eval(x);
  }
};
struct st {
  st *left, *right;
  int l, r, m;
  cht trick;
  st(int l, int r) : l(l), r(r) {
    m = (l + r) / 2;
    if (l != r) {
      left = new st(l, m);
      right = new st(m + 1, r);
    }
  }
  void update(int a, int b, line &L) {
    if (a > b) return;
    if (a == l && b == r) {
      trick.add(L);
    } else {
      if (b <= m)
        left->update(a, b, L);
      else if (a > m)
        right->update(a, b, L);
      else
        left->update(a, m, L), right->update(m + 1, b, L);
    }
  }
  long long get(int a, long long x) {
    long long R = trick.get_max(x);
    if (l == r) return R;
    if (a <= m) return max(R, left->get(a, x));
    return max(R, right->get(a, x));
  }
};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  while (cin >> n) {
    vector<int> from(n, n + 1), to(n, n);
    vector<line> v(n);
    vector<pair<int, int> > queries;
    for (int i = 0; i < n; i++) {
      int cmd;
      cin >> cmd;
      if (cmd == 1) cin >> v[i].m >> v[i].b, from[i] = i;
      if (cmd == 2) {
        int j;
        cin >> j;
        j--;
        to[j] = i;
      }
      if (cmd == 3) {
        long long x;
        cin >> x;
        queries.push_back({x, i});
      }
    }
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(),
         [&](int a, int b) { return v[a].m < v[b].m; });
    st tree(0, n);
    for (int i = 0; i < n; i++) {
      int I = order[i];
      tree.update(from[I], to[I], v[I]);
    }
    for (auto &q : queries) {
      long long ans = tree.get(q.second, q.first);
      if (ans == LLONG_MIN)
        cout << "EMPTY SET" << '\n';
      else
        cout << ans << '\n';
    }
  }
}