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;
vector<pair<int, int> > tree[1050000];
void add(int s, int e, int ps, int pe, int p, pair<int, int> v) {
  if (e < ps || pe < s) return;
  if (s <= ps && pe <= e) {
    tree[p].push_back(v);
    return;
  }
  int pm = (ps + pe) / 2;
  add(s, e, ps, pm, 2 * p, v);
  add(s, e, pm + 1, pe, 2 * p + 1, v);
}
vector<pair<int, int> > tmp;
bool ok(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
  return 1ll * (b.first - a.first) * (c.second - b.second) <=
         1ll * (b.first - c.first) * (a.second - b.second);
}
void solve(int x) {
  sort(tree[x].begin(), tree[x].end(),
       [&](const pair<int, int> &a, const pair<int, int> &b) {
         return pair<int, int>(a.first, -a.second) <
                pair<int, int>(b.first, -b.second);
       });
  tmp.clear();
  int pv = -2e9;
  for (auto &i : tree[x]) {
    if (i.first == pv) continue;
    pv = i.first;
    while (tmp.size() >= 2 && !ok(tmp[tmp.size() - 2], tmp.back(), i)) {
      tmp.pop_back();
    }
    tmp.push_back(i);
  }
  tree[x] = tmp;
}
void dfs(int s, int e, int p) {
  solve(p);
  if (s == e) return;
  int m = (s + e) / 2;
  dfs(s, m, 2 * p);
  dfs(m + 1, e, 2 * p + 1);
}
long long nodequery(int p, int x) {
  if (tree[p].empty()) return -5e18;
  auto func = [&](int q) {
    return 1ll * tree[p][q].first * x + tree[p][q].second;
  };
  int s = 0, e = (int)tree[p].size() - 1;
  while (s != e) {
    int m = (s + e) / 2;
    if (func(m) < func(m + 1))
      s = m + 1;
    else
      e = m;
  }
  return func(s);
}
long long query(int pos, int s, int e, int p, int x) {
  long long ret = nodequery(p, x);
  if (s == e) return ret;
  int m = (s + e) / 2;
  if (pos <= m)
    ret = max(ret, query(pos, s, m, 2 * p, x));
  else
    ret = max(ret, query(pos, m + 1, e, 2 * p + 1, x));
  return ret;
}
struct ins {
  int s, e, x, y;
};
int q;
vector<ins> inserts;
pair<int, int> inslis[300005];
bool vis[300005];
int cnt[300005], qry[300005];
int main() {
  int inp;
  cin >> inp;
  for (int i = 1; i <= inp; i++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      vis[i] = 1;
      scanf("%d %d", &inslis[i].first, &inslis[i].second);
    }
    if (t == 2) {
      int x;
      scanf("%d", &x);
      inserts.push_back(
          {cnt[x] + 1, cnt[i - 1], inslis[x].first, inslis[x].second});
      vis[x] = 0;
    }
    if (t == 3) {
      scanf("%d", &qry[i]);
      cnt[i]++;
    }
    cnt[i] += cnt[i - 1];
  }
  if (cnt[inp] == 0) return 0;
  for (int i = 1; i <= inp; i++) {
    if (vis[i]) {
      inserts.push_back(
          {cnt[i] + 1, cnt[inp], inslis[i].first, inslis[i].second});
    }
  }
  for (auto &i : inserts) {
    add(i.s, i.e, 1, cnt[inp], 1, pair<int, int>(i.x, i.y));
  }
  dfs(1, cnt[inp], 1);
  for (int i = 1; i <= inp; i++) {
    if (cnt[i] != cnt[i - 1]) {
      long long t = query(cnt[i], 1, cnt[inp], 1, qry[i]);
      if (t < -4e18)
        puts("EMPTY SET");
      else
        printf("%lld\n", t);
    }
  }
}