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;
static const int maxn = 4e5 + 5;
static const long long int is_query = LLONG_MIN;
struct Line {
  long long int m, b;
  mutable function<const Line *()> succ;
  bool operator<(const Line &rhs) const {
    if (rhs.b != is_query) return m < rhs.m;
    const Line *s = succ();
    if (!s) return 0;
    long long int x = rhs.m;
    return (b - s->b) < ((s->m - m) * x);
  }
};
struct CHT : public multiset<Line> {
  bool bad(iterator y) {
    auto z = next(y);
    if (y == begin()) {
      if (z == end()) return 0;
      return y->m == z->m && y->b <= z->b;
    }
    auto x = prev(y);
    if (z == end()) return y->m == x->m && y->b <= x->b;
    return 1.0 * (x->b - y->b) * (z->m - y->m) >=
           1.0 * (y->b - z->b) * (y->m - x->m);
  }
  void add(long long int m, long long int b) {
    auto y = insert({m, b});
    y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
    if (bad(y)) {
      erase(y);
      return;
    }
    while (next(y) != end() && bad(next(y))) erase(next(y));
    while (y != begin() && bad(prev(y))) erase(prev(y));
  }
  long long int query(long long int x) {
    auto l = *lower_bound((Line){x, is_query});
    return l.m * x + l.b;
  }
};
vector<vector<pair<long long int, long long int> > > Tree(4 * maxn);
void update(int node, int a, int b, int i, int j,
            pair<long long int, long long int> p) {
  if (a > j or b < i) return;
  if (a >= i and b <= j) return void(Tree[node].push_back(p));
  int lchild = node * 2;
  int rchild = lchild + 1;
  int mid = (a + b) / 2;
  update(lchild, a, mid, i, j, p);
  update(rchild, mid + 1, b, i, j, p);
}
CHT *cht[30];
long long int qval[maxn];
bool valid[maxn];
long long int ans[maxn];
bool isquery[maxn];
void dfs(int node, int a, int b, int h) {
  if (a > b) return;
  cht[h] = new CHT();
  for (pair<long long int, long long int> p : Tree[node])
    (*cht[h]).add(p.first, p.second);
  if (a == b) {
    if (isquery[a] == 0) return;
    long long int maxi = is_query;
    for (int i = 0; i <= h; i++) {
      if ((*cht[i]).size() == 0) continue;
      long long int dp = (*cht[i]).query(qval[a]);
      maxi = max(maxi, dp);
      valid[a] = 1;
    }
    ans[a] = maxi;
  } else {
    int lchild = node * 2;
    int rchild = lchild + 1;
    int mid = (a + b) / 2;
    dfs(lchild, a, mid, h + 1);
    dfs(rchild, mid + 1, b, h + 1);
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  map<pair<long long int, long long int>, int> in;
  vector<pair<long long int, long long int> > all_queries(n + 1);
  for (int i = 1; i <= n; i++) {
    int type;
    cin >> type;
    if (type == 1) {
      long long int a, b;
      cin >> a >> b;
      in[make_pair(a, b)] = i;
      all_queries[i] = make_pair(a, b);
    } else if (type == 2) {
      int id;
      cin >> id;
      long long int a = all_queries[id].first;
      long long int b = all_queries[id].second;
      int l = in[make_pair(a, b)];
      int r = i - 1;
      update(1, 1, n, l, r, make_pair(a, b));
      in.erase(make_pair(a, b));
    } else {
      long long int val;
      cin >> val;
      qval[i] = val;
      isquery[i] = 1;
    }
  }
  for (auto it : in) {
    int l = it.second;
    int r = n;
    long long int a = it.first.first;
    long long int b = it.first.second;
    update(1, 1, n, l, r, make_pair(a, b));
  }
  dfs(1, 1, n, 0);
  for (int i = 1; i <= n; i++) {
    if (isquery[i] == 0) continue;
    if (valid[i])
      cout << ans[i] << '\n';
    else
      cout << "EMPTY SET" << '\n';
  }
}