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;
const long long inf = 3e18;
const int inf2 = 1e9 + 2;
const int mod = 1000000007;
inline int mf(int a, int b) {
  int buf = 0;
  if (a % b != 0) buf++;
  if ((a >= 0 && b >= 0) || (a < 0 && b < 0)) return a / b + buf;
  return a / b;
}
pair<int, int> ma[300003];
int cht[300003];
pair<int, int> cht_inf[300003];
int need_ans[300003];
pair<int, pair<int, int> > nnew[300003];
int nnew_pos = 0, need_ans_pos = 0, answ_pos, cht_pos, all_pos, all2_pos;
long long answ[300003];
int answ2[300003];
pair<int, pair<int, int> > all[300003];
pair<int, pair<int, int> > all2[300003];
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  int dop = 800;
  vector<char> used(n);
  vector<long long> answw;
  int pos = 0;
  for (int c = 0; c < n; c += dop) {
    int r = min(n, c + dop);
    need_ans_pos = 0;
    nnew_pos = 0;
    answ_pos = 0;
    cht_pos = 0;
    all2_pos = 0;
    for (int k = c; k < r; k++) {
      int t;
      cin >> t;
      if (t == 1) {
        int a, b;
        cin >> a >> b;
        nnew[nnew_pos++] = {a, {b, k}};
        ma[k] = {a, b};
      }
      if (t == 2) {
        int a;
        cin >> a;
        used[a - 1] = true;
        for (int i = 0; i < need_ans_pos; i++) {
          if (answ2[i] < a) continue;
          answ[i] = max(answ[i],
                        ma[a - 1].first * 1ll * need_ans[i] + ma[a - 1].second);
        }
      }
      if (t == 3) {
        int a;
        cin >> a;
        need_ans[need_ans_pos++] = a;
        answ[answ_pos] = -inf;
        answ2[answ_pos++] = k;
        int y = answ_pos - 1;
        for (int j = 0; j < nnew_pos; j++) {
          if (!used[nnew[j].second.second]) {
            answ[y] =
                max(answ[y], a * 1ll * nnew[j].first + nnew[j].second.first);
          }
        }
      }
    }
    for (int j = 0; j < all_pos; j++) {
      auto i = all[j];
      if (cht_pos && cht_inf[cht_pos - 1].first == i.first) {
        cht_pos--;
      }
      if (used[i.second.second]) continue;
      while (cht_pos > 1) {
        pair<int, int> lt = {cht_inf[cht_pos - 1].first,
                             cht_inf[cht_pos - 1].second};
        int xnew = mf(i.second.first - lt.second, lt.first - i.first);
        if (xnew < cht[cht_pos - 1]) {
          cht_pos--;
        } else
          break;
      }
      if (cht_pos == 0) {
        cht[cht_pos] = -inf2;
        cht_inf[cht_pos++] = {i.first, i.second.first};
        continue;
      }
      pair<int, int> lt = {cht_inf[cht_pos - 1].first,
                           cht_inf[cht_pos - 1].second};
      int xnew = mf(i.second.first - lt.second, lt.first - i.first);
      cht[cht_pos] = xnew;
      cht_inf[cht_pos++] = {i.first, i.second.first};
    }
    int u = 0;
    for (int j = 0; j < need_ans_pos; j++) {
      int i = need_ans[j];
      if (!cht_pos) break;
      int l = 0, r = cht_pos;
      while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (cht[mid] <= i)
          l = mid;
        else
          r = mid;
      }
      answ[u] = max(answ[u],
                    need_ans[u] * 1ll * cht_inf[l].first + cht_inf[l].second);
      u++;
    }
    for (int j = 0; j < answ_pos; j++) {
      answw.push_back(answ[j]);
    }
    sort(nnew, nnew + nnew_pos);
    int l1 = 0, l2 = 0;
    while (l1 < all_pos && l2 < nnew_pos) {
      if (all[l1] < nnew[l2]) {
        all2[all2_pos++] = all[l1++];
      } else
        all2[all2_pos++] = nnew[l2++];
    }
    while (l1 < all_pos) all2[all2_pos++] = all[l1++];
    while (l2 < nnew_pos) all2[all2_pos++] = nnew[l2++];
    for (int c = 0; c < all2_pos; c++) all[c] = all2[c];
    all_pos = all2_pos;
    pos++;
  }
  for (auto i : answw) {
    if (i == -inf)
      cout << "EMPTY SET\n";
    else
      cout << i << "\n";
  }
  return 0;
}