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;
bool SR(int &_x) { return scanf("%d", &_x) == 1; }
bool SR(long long &_x) { return scanf("%" PRId64, &_x) == 1; }
bool SR(double &_x) { return scanf("%lf", &_x) == 1; }
bool SR(char *_s) { return scanf("%s", _s) == 1; }
bool RI() { return true; }
template <typename I, typename... T>
bool RI(I &_x, T &..._tail) {
  return SR(_x) && RI(_tail...);
}
void SP(const int _x) { printf("%d", _x); }
void SP(const long long _x) { printf("%" PRId64, _x); }
void SP(const double _x) { printf("%.16lf", _x); }
void SP(const char *s) { printf("%s", s); }
void PL() { puts(""); }
template <typename I, typename... T>
void PL(const I _x, const T... _tail) {
  SP(_x);
  if (sizeof...(_tail)) putchar(' ');
  PL(_tail...);
}
const int maxn = 3e5 + 5;
bool win(const pair<int, int> &i, const pair<int, int> &j,
         const pair<int, int> &k) {
  assert(i.first < j.first && j.first < k.first);
  return 1LL * (i.second - j.second) * (k.first - j.first) >=
         1LL * (j.second - k.second) * (j.first - i.first);
}
long long f(const pair<int, int> &p, const int &x) {
  return 1LL * p.first * x + p.second;
}
const long long INF = 2e18;
struct Seg {
  vector<pair<int, int> > dat[maxn << 2];
  void add(int x, int low, int high, int a, int b, pair<int, int> v) {
    if (low == a && b == high) {
      ;
      dat[x].push_back(v);
      return;
    }
    int mid = (low + high) / 2;
    if (b <= mid)
      add(x << 1, low, mid, a, b, v);
    else if (mid + 1 <= a)
      add(x << 1 | 1, mid + 1, high, a, b, v);
    else
      add(x << 1, low, mid, a, mid, v),
          add(x << 1 | 1, mid + 1, high, mid + 1, b, v);
  }
  void build(int x, int low, int high) {
    dat[x].erase(unique((dat[x]).begin(), (dat[x]).end(),
                        [&](pair<int, int> a, pair<int, int> b) {
                          return a.first == b.first;
                        }),
                 dat[x].end());
    vector<pair<int, int> > q;
    for (auto p : dat[x]) {
      while (((int)(q).size()) >= 2 &&
             win(q[((int)(q).size()) - 2], q.back(), p))
        q.pop_back();
      q.push_back(p);
    }
    dat[x].swap(q);
    reverse((dat[x]).begin(), (dat[x]).end());
    if (low == high) return;
    int mid = (low + high) / 2;
    build(x << 1, low, mid);
    build(x << 1 | 1, mid + 1, high);
  }
  long long ask(int x, int low, int high, int pos, int val) {
    while (((int)(dat[x]).size()) >= 2 &&
           f(dat[x][((int)(dat[x]).size()) - 2], val) >= f(dat[x].back(), val))
      dat[x].pop_back();
    long long ret = (((int)(dat[x]).size()) ? f(dat[x].back(), val) : -INF);
    if (low == high) return ret;
    int mid = (low + high) / 2;
    if (pos <= mid)
      return max(ret, ask(x << 1, low, mid, pos, val));
    else
      return max(ret, ask(x << 1 | 1, mid + 1, high, pos, val));
  }
} seg;
int n;
int a[maxn][3];
void read() {
  RI(n);
  for (int i = (1); i <= int(n); i++) {
    RI(a[i][0], a[i][1]);
    if (a[i][0] == 1) RI(a[i][2]);
  }
}
void build() {
  map<pair<int, int>, int> hp, st;
  vector<pair<pair<int, int>, pair<int, int> > > v;
  for (int i = (1); i <= int(n); i++) {
    if (a[i][0] == 1) {
      if (++hp[make_pair(a[i][1], a[i][2])] == 1)
        st[make_pair(a[i][1], a[i][2])] = i;
    } else if (a[i][0] == 2) {
      auto p = make_pair(a[a[i][1]][1], a[a[i][1]][2]);
      if (--hp[p] == 0) v.push_back(make_pair(p, make_pair(st[p], i)));
    }
  }
  for (auto p : hp)
    if (p.second > 0)
      v.push_back(make_pair(p.first, make_pair(st[p.first], n)));
  sort((v).begin(), (v).end(),
       [&](const pair<pair<int, int>, pair<int, int> > &x,
           const pair<pair<int, int>, pair<int, int> > &y) {
         return tie(x.first.first, y.first.second) <
                tie(y.first.first, x.first.second);
       });
  for (auto p : v) {
    seg.add(1, 1, n, p.second.first, p.second.second, p.first);
    ;
  }
  seg.build(1, 1, n);
}
long long ans[maxn];
void sol() {
  vector<int> v;
  for (int i = (1); i <= int(n); i++)
    if (a[i][0] == 3) v.push_back(i);
  sort((v).begin(), (v).end(), [&](int i, int j) { return a[i][1] < a[j][1]; });
  for (int i : v) ans[i] = seg.ask(1, 1, n, i, a[i][1]);
  for (int i = (1); i <= int(n); i++)
    if (a[i][0] == 3) {
      if (ans[i] == -INF)
        PL("EMPTY SET");
      else
        PL(ans[i]);
    }
}
int main() {
  read();
  build();
  sol();
  return 0;
}