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;
inline int read() {
  register int X = 0;
  register char ch = 0, w = 0;
  while (ch < 48 || ch > 57) ch = getchar(), w |= (ch == '-');
  while (ch >= 48 && ch <= 57) X = X * 10 + (ch ^ 48), ch = getchar();
  return w ? -X : X;
}
struct Line {
  int k, b;
  double t;
  long long get(int x) { return 1ll * k * x + b; }
} q[300500];
vector<Line> a[300500 << 2];
int wfl, wfr, qry[300500], tot;
Line wfc;
void addop(int l = 1, int r = tot, int num = 1) {
  if (wfl <= l && r <= wfr) {
    a[num].push_back(wfc);
    return;
  }
  int mid = (l + r) >> 1;
  if (wfl <= mid) addop(l, mid, num << 1);
  if (mid < wfr) addop(mid + 1, r, num << 1 | 1);
}
bool cmp(const Line &A, const Line &B) { return A.k < B.k; }
double inter(const Line &A, const Line &B) {
  if (A.k == B.k) return A.b > B.b ? 1e18 : -1e18;
  return 1.00 * (B.b - A.b) / (A.k - B.k);
}
long long ans[300500];
void solve(int l = 1, int r = tot, int num = 1) {
  int top = 0;
  sort(a[num].begin(), a[num].end(), cmp);
  for (int i = 0; i < a[num].size(); i++) {
    Line sav = a[num][i];
    while (top > 1 && q[top].t + 1e-12 > inter(q[top], sav)) top--;
    q[++top] = sav;
    if (top == 1)
      q[top].t = -1e18;
    else
      q[top].t = inter(q[top - 1], q[top]);
  }
  if (top) {
    for (int i = l; i <= r; i++) {
      int tl = 1, tr = top, mid;
      while (tl < tr) {
        mid = (tl + tr + 1) >> 1;
        if (q[mid].t < qry[i] + 1e-12)
          tl = mid;
        else
          tr = mid - 1;
      }
      ans[i] = max(ans[i], q[tr].get(qry[i]));
    }
  }
  if (l == r) {
    if (ans[l] == (-1ll << 60))
      puts("EMPTY SET");
    else
      printf("%lld\n", ans[l]);
    return;
  }
  int mid = (l + r) >> 1;
  solve(l, mid, num << 1);
  solve(mid + 1, r, num << 1 | 1);
}
struct Data {
  Line x;
  int l, r;
} s[300500];
int m;
int main() {
  scanf("%d", &m);
  for (int i = 1, op; i <= m; i++) {
    op = read();
    if (op == 1) {
      s[i].x.k = read();
      s[i].x.b = read();
      s[i].l = tot + 1;
      s[i].r = -1;
    }
    if (op == 2) s[read()].r = tot;
    if (op == 3) {
      qry[++tot] = read();
      ans[tot] = -1ll << 60;
    }
  }
  for (int i = 1; i <= m; i++) {
    if (s[i].l) {
      wfl = s[i].l;
      wfc = s[i].x;
      wfr = (s[i].r == -1) ? tot : s[i].r;
      if (wfl <= wfr) addop();
    }
  }
  if (tot) solve();
  return 0;
}