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>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
mt19937 ggen;
struct query {
  int type;
  long long a, b;
  query() {}
  query(int type, long long a = 0, long long b = 0) : type(type), a(a), b(b) {}
};
bool double_eq(const double &a, const double &b) { return fabs(a - b) < 1e-9; }
bool double_le(const double &a, const double &b) { return a < b - 1e-9; }
bool double_leq(const double &a, const double &b) { return a < b + 1e-9; }
bool double_gr(const double &a, const double &b) { return a > b + 1e-9; }
bool double_greq(const double &a, const double &b) { return a > b - 1e-9; }
int n;
query q[500010];
struct fun {
  long long a, b;
  fun() {}
  fun(long long a, long long b) : a(a), b(b) {}
  long long val(long long q) { return a * q + b; }
};
bool operator<(const fun &f1, const fun &f2) {
  if (f1.a < f2.a)
    return 1;
  else if (f1.a == f2.a && f1.b < f2.b)
    return 1;
  else
    return 0;
}
int root;
vector<pair<double, fun> > ch;
vector<fun> fv;
vector<int> st;
int del[500010];
int timer;
inline double operator*(const fun &f1, const fun &f2) {
  if (f1.a == f2.a)
    return -((long long)(2e18) + 1337);
  else
    return (double)(f2.b - f1.b) / (f1.a - f2.a);
}
void build_ch() {
  ch.clear();
  sort(fv.begin(), fv.end());
  for (int i = 0; i < (int)fv.size(); i++) {
    while (!ch.empty() &&
           double_leq((ch.back().second * fv[i]), ch.back().first))
      ch.pop_back();
    if (ch.empty())
      ch.push_back(make_pair(-(double)((long long)(2e18) + 1337), fv[i]));
    else
      ch.push_back(make_pair(ch.back().second * fv[i], fv[i]));
  }
}
bool comp(const pair<double, fun> &a, const pair<double, fun> &b) {
  return double_le(a.first, b.first);
}
long long get_ch(long long x) {
  if (ch.size() == 0) return -((long long)(2e18) + 1337);
  if (ch.size() == 1) return ch.back().second.val(x);
  auto it =
      upper_bound(ch.begin(), ch.end(), pair<double, fun>(x, fun()), comp) - 1;
  return it->second.val(x);
}
long long get_st(long long x) {
  long long res = -((long long)(2e18) + 1337);
  for (int i = 0; i < (int)st.size(); i++) {
    int ix = st[i];
    if (del[ix] != timer) res = max(res, q[ix].a * x + q[ix].b);
  }
  return res;
}
void rebuild(int pos) {
  timer++;
  fv.clear();
  st.clear();
  ch.clear();
  for (int i = 0; i < n && i - pos < root; i++) {
    if (q[i].type == 2) {
      del[q[i].a - 1] = timer;
    }
  }
  for (int i = 0; i < pos; i++) {
    if (q[i].type == 1 && !del[i]) {
      fv.push_back(fun(q[i].a, q[i].b));
    }
  }
  build_ch();
  for (int i = pos; i < n && i - pos < root; i++) {
    int ix = (int)(q[i].a) - 1;
    if (q[i].type == 2 && ix < pos) st.push_back(ix);
  }
}
void solve() {
  ch.reserve(500000);
  st.reserve(500000);
  fv.reserve(500000);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> q[i].type;
    if (q[i].type == 1)
      cin >> q[i].a >> q[i].b;
    else
      cin >> q[i].a;
  }
  root = 3000;
  for (int i = 0; i < n; i++) {
    if ((i % root) == 0) {
      rebuild(i);
      timer++;
    }
    if (q[i].type == 1) {
      st.push_back(i);
    } else if (q[i].type == 2) {
      del[q[i].a - 1] = timer;
    } else {
      long long ans = max(get_ch(q[i].a), get_st(q[i].a));
      if (ans == -((long long)(2e18) + 1337))
        cout << "EMPTY SET\n";
      else
        cout << ans << '\n';
    }
  }
}
void testgen(int n) {
  ofstream ofs("input.txt", ios_base::out | ios_base::trunc);
  mt19937 gen(1337);
  ofs << n << '\n';
  uniform_int_distribution<int> distr((int)(-1e9), (int)(1e9));
  uniform_int_distribution<int> distr2(0, 1);
  for (int i = 0; i < n; i++) {
    if (distr2(gen)) {
      ofs << "1 " << distr(gen) << ' ' << distr(gen) << '\n';
    } else {
      ofs << "3 " << distr(gen) << '\n';
    }
  }
  ofs.close();
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  srand(1313);
  ggen = mt19937(13);
  solve();
  return 0;
}