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;
using ll = long long;
template <typename T, const T id>
class retroactive_CHT {
  struct line {
    T a, b;
    line(T a_ = 0, T b_ = 0) : a(a_), b(b_) {}
    T get(T x) const { return a * x + b; }
  };
  const int n;
  const vector<T> pos;
  vector<line> data;
  vector<pair<int, line>> hist;
  void modify(int p, int lb, int ub, line& l) {
    if (data[p].a == id) {
      hist.emplace_back(p, move(data[p]));
      data[p] = move(l);
      return;
    }
    if (data[p].get(pos[lb]) >= l.get(pos[lb]) &&
        data[p].get(pos[ub - 1]) >= l.get(pos[ub - 1]))
      return;
    if (data[p].get(pos[lb]) <= l.get(pos[lb]) &&
        data[p].get(pos[ub - 1]) <= l.get(pos[ub - 1])) {
      hist.emplace_back(p, move(data[p]));
      data[p] = move(l);
      return;
    }
    int c = (lb + ub) >> 1;
    if (data[p].get(pos[c]) < l.get(pos[c])) {
      line tmp = data[p];
      hist.emplace_back(p, move(data[p]));
      data[p] = move(l);
      l = move(tmp);
    }
    if (data[p].get(pos[lb]) <= l.get(pos[lb]))
      modify(p << 1, lb, c, l);
    else
      modify((p << 1) | 1, c, ub, l);
  }
  T sub(int p, int lb, int ub, int t) const {
    if (data[p].a == id) return id;
    if (ub - lb == 1) return data[p].get(pos[t]);
    int c = (lb + ub) >> 1;
    if (t < c) return max(data[p].get(pos[t]), sub(p << 1, lb, c, t));
    return max(data[p].get(pos[t]), sub((p << 1) | 1, c, ub, t));
  }

 public:
  retroactive_CHT(const vector<T>& pos_)
      : n(pos_.size()), pos(pos_), data(n << 2, line(id, id)) {}
  void insert(T a, T b) {
    line l(a, b);
    modify(1, 0, n, l);
  }
  T get(T x) const {
    int t = lower_bound(pos.begin(), pos.end(), x) - pos.begin();
    assert(t < n && pos[t] == x);
    return sub(1, 0, n, t);
  }
  int get_version() const { return hist.size(); }
  void rollback(int ver) {
    assert(0 <= ver && ver <= (int)hist.size());
    int cnt = hist.size() - ver;
    while (cnt--) {
      data[hist.back().first] = hist.back().second;
      hist.pop_back();
    }
  }
};
using CHT = retroactive_CHT<ll, LLONG_MIN>;
const int MAX = 1 << 19;
vector<pair<int, int>> lines[MAX << 1];
int used[MAX];
int que[MAX];
vector<ll> res;
void add_range_line(int l, int r, int a, int b, int p = 1, int lb = 0,
                    int ub = MAX) {
  if (r <= lb || ub <= l) return;
  if (l <= lb && ub <= r) {
    lines[p].emplace_back(a, b);
    return;
  }
  add_range_line(l, r, a, b, p << 1, lb, (lb + ub) >> 1);
  add_range_line(l, r, a, b, (p << 1) | 1, (lb + ub) >> 1, ub);
}
void dfs(int p, CHT& cht) {
  int ver = cht.get_version();
  for (auto l : lines[p]) {
    cht.insert(l.first, l.second);
  }
  if (p >= MAX) {
    if (used[p - MAX]) {
      res.push_back(cht.get(que[p - MAX]));
    }
  } else {
    dfs(p << 1, cht);
    dfs((p << 1) | 1, cht);
  }
  cht.rollback(ver);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  vector<int> ex(n);
  vector<ll> pos;
  for (int i = 0; i < n; i++) {
    int t;
    cin >> t;
    if (t == 1) {
      cin >> a[i] >> b[i];
      ex[i] = 1;
    } else if (t == 2) {
      int x;
      cin >> x;
      --x;
      add_range_line(x, i, a[x], b[x]);
      ex[x] = 0;
    } else {
      int x;
      cin >> x;
      pos.push_back(x);
      used[i] = 1;
      que[i] = x;
    }
  }
  for (int i = 0; i < n; i++)
    if (ex[i]) {
      add_range_line(i, n, a[i], b[i]);
    }
  sort(pos.begin(), pos.end());
  pos.erase(unique(pos.begin(), pos.end()), pos.end());
  if (pos.empty()) {
    return 0;
  }
  CHT cht(pos);
  dfs(1, cht);
  for (auto& ans : res) {
    if (ans == LLONG_MIN) {
      puts("EMPTY SET");
    } else {
      printf("%lld\n", ans);
    }
  }
  return 0;
}