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;
struct CHT {
 public:
  vector<pair<int, int> > lines;

 public:
  CHT() {}
  void addLine(pair<int, int> line) { lines.push_back(line); }
  void build() {
    sort(lines.begin(), lines.end());
    vector<pair<int, int> > _lines = lines;
    lines.clear();
    for (pair<int, int> line : _lines) insert(line);
  }
  long long query(int first) {
    if (lines.empty()) return LLONG_MIN;
    int L = 0, R = lines.size() - 1;
    while (L != R) {
      int mid1 = L + (R - L) / 3;
      int mid2 = R - (R - L) / 3;
      if (lines[mid1].first * 1LL * first + lines[mid1].second >=
          lines[mid2].first * 1LL * first + lines[mid2].second)
        R = mid2 - 1;
      else
        L = mid1 + 1;
    }
    return lines[L].first * 1LL * first + lines[L].second;
  }

 private:
  bool bad(pair<int, int> line1, pair<int, int> line2, pair<int, int> line3) {
    return (line3.second - line1.second) * 1LL * (line1.first - line2.first) <=
           (line2.second - line1.second) * 1LL * (line1.first - line3.first);
  }
  void insert(pair<int, int> line) {
    while (lines.size() > 0 && lines.back().first == line.first)
      lines.pop_back();
    lines.push_back(line);
    int sz = lines.size();
    while (sz >= 3 && bad(lines[sz - 3], lines[sz - 2], lines[sz - 1])) {
      lines.erase(lines.end() - 2);
      sz--;
    }
  }
};
const int N = int(3e5) + 10;
int n;
map<int, pair<int, int> > line_at_query;
vector<pair<int, int> > queries;
CHT st[4 * N];
void build(int stI, int L, int R) {
  st[stI].build();
  if (L == R) return;
  int mid = (L + R) / 2;
  build((stI << 1), L, mid);
  build((stI << 1) + 1, mid + 1, R);
}
void build() { build(1, 1, n); }
void insert(int stI, int L, int R, int l, int r, pair<int, int> val) {
  if (r < L || R < l) return;
  if (l <= L && R <= r) {
    st[stI].addLine(val);
    return;
  }
  int mid = (L + R) / 2;
  insert((stI << 1), L, mid, l, r, val);
  insert((stI << 1) + 1, mid + 1, R, l, r, val);
}
void insert(int l, int r, pair<int, int> val) { insert(1, 1, n, l, r, val); }
long long query(int stI, int L, int R, int at, int first) {
  if (at < L || R < at) return LLONG_MIN;
  if (L == R) return st[stI].query(first);
  long long ret = st[stI].query(first);
  int mid = (L + R) / 2;
  ret = max(ret, query((stI << 1), L, mid, at, first));
  ret = max(ret, query((stI << 1) + 1, mid + 1, R, at, first));
  return ret;
}
long long query(int at, int first) { return query(1, 1, n, at, first); }
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int a, b;
      scanf("%d %d", &a, &b);
      line_at_query[i] = make_pair(a, b);
    } else if (t == 2) {
      int _i;
      scanf("%d", &_i);
      insert(_i, i, line_at_query[_i]);
      line_at_query.erase(_i);
    } else if (t == 3) {
      int q;
      scanf("%d", &q);
      queries.push_back(make_pair(i, q));
    }
  }
  for (auto item : line_at_query) {
    insert(item.first, n, item.second);
  }
  build();
  for (pair<int, int> p : queries) {
    long long ans = query(p.first, p.second);
    if (ans == LLONG_MIN)
      puts("EMPTY SET");
    else
      printf("%lld\n", ans);
  }
  return 0;
}