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 op {
  int tp;
  int a, b, x;
  int id;
  void read() {
    scanf("%d", &tp);
    if (tp == 1)
      scanf("%d%d", &a, &b);
    else
      scanf("%d", &x);
  }
};
int n, i, bucket_size;
op Q[300011];
map<pair<int, int>, int> M;
vector<pair<int, int> > lines;
int cnt[300011];
vector<int> to_process;
long long ans[300011];
void hull_and_solve(int l, int r) {
  static vector<pair<int, int> > work;
  static vector<pair<long long, int> > hull;
  long long a1, a2, b1, b2, lmt;
  int i;
  work.clear();
  for (i = 0; i < lines.size(); i++)
    if (cnt[i]) work.push_back(lines[i]);
  if (work.empty()) return;
  hull = {make_pair(-(1LL << 60), 0)};
  for (i = 1; i < work.size(); i++) {
    if (work[hull.back().second].first == work[i].first) {
      hull[hull.size() - 1].second = i;
      continue;
    }
    a2 = work[i].first;
    b2 = work[i].second;
    while (hull.size() > 0) {
      a1 = work[hull.back().second].first;
      b1 = work[hull.back().second].second;
      lmt = (b1 - b2 + a2 - a1 - 1) / (a2 - a1);
      if (lmt > hull.back().first) break;
      hull.pop_back();
    }
    hull.push_back(make_pair(lmt, i));
  }
  for (i = l; i <= r; i++) {
    if (Q[i].tp != 3) continue;
    int pos =
        upper_bound(hull.begin(), hull.end(), make_pair(1LL * Q[i].x, n + 1)) -
        hull.begin();
    pos--;
    ans[i] = 1LL * work[hull[pos].second].first * Q[i].x +
             1LL * work[hull[pos].second].second;
  }
}
void solve_bucket(int l, int r) {
  int i;
  to_process.clear();
  for (i = l; i <= r; i++) {
    if (Q[i].tp == 3) {
      ans[i] = -(1LL << 60);
      continue;
    }
    if (Q[i].tp == 1) {
      to_process.push_back(i);
      continue;
    }
    to_process.push_back(Q[i].x);
    if (Q[i].x < l) cnt[Q[Q[i].x].id]--;
  }
  hull_and_solve(l, r);
  for (i = l; i <= r; i++)
    if (Q[i].tp == 2)
      if (Q[i].x < l) cnt[Q[Q[i].x].id]++;
  for (i = l; i <= r; i++) {
    if (Q[i].tp == 1) {
      cnt[Q[i].id]++;
      continue;
    }
    if (Q[i].tp == 2) {
      cnt[Q[Q[i].x].id]--;
      continue;
    }
    for (auto e : to_process) {
      if (cnt[Q[e].id] == 0) continue;
      ans[i] = max(ans[i], 1LL * Q[e].a * Q[i].x + 1LL * Q[e].b);
    }
    if (ans[i] == -(1LL << 60))
      printf("EMPTY SET\n");
    else
      printf("%lld\n", ans[i]);
  }
}
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    Q[i].read();
    if (Q[i].tp == 1) lines.push_back(make_pair(Q[i].a, Q[i].b));
  }
  sort(lines.begin(), lines.end());
  lines.resize(unique(lines.begin(), lines.end()) - lines.begin());
  M.clear();
  for (i = 0; i < lines.size(); i++) M[lines[i]] = i;
  for (i = 1; i <= n; i++)
    if (Q[i].tp == 1) Q[i].id = M[make_pair(Q[i].a, Q[i].b)];
  bucket_size = 5 * sqrt(n);
  for (i = 1; i <= n; i += bucket_size)
    solve_bucket(i, min(n, i + bucket_size - 1));
  return 0;
}