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;
int convexP = 0;
const int SQ = 1075;
const long long mini = -8e18;
bool isErased[300001];
long long type[300001], a[300001], b[300001];
long long out[300001];
long long la[300001], lb[300001];
int convexSz, p;
double cross(int x, int y) { return (double)(lb[y] - lb[x]) / (la[x] - la[y]); }
void insert(long long m, long long b) {
  if (convexSz > 0) {
    if (la[convexSz - 1] == m) {
      lb[convexSz - 1] = min(lb[convexSz - 1], b);
    } else {
      la[convexSz] = m;
      lb[convexSz++] = b;
    }
  } else {
    la[convexSz] = m;
    lb[convexSz++] = b;
  }
  while (convexSz >= 3 && cross(convexSz - 3, convexSz - 2) >
                              cross(convexSz - 2, convexSz - 1)) {
    swap(la[convexSz - 2], la[convexSz - 1]);
    swap(lb[convexSz - 2], lb[convexSz - 1]);
    --convexSz;
  }
}
long long query(long long x) {
  if (convexSz == 0) {
    return mini;
  }
  while (p + 1 < convexSz && cross(p, p + 1) <= x) p++;
  return -(lb[p] + la[p] * x);
}
pair<pair<long long, long long>, int> ret[300001];
pair<pair<long long, long long>, int> v[300001];
pair<pair<long long, long long>, int> u[300001];
pair<pair<long long, long long>, int> g[300001];
void merge(int &arSize, int st, int ed) {
  int usz = 0;
  for (int i = st; i <= ed; ++i) {
    if (!isErased[i] && type[i] == 1) {
      u[usz++] = {{-a[i], -b[i]}, i};
    }
  }
  sort(u, u + usz, greater<pair<pair<int, int>, int> >());
  int sz0 = 0, sz1 = 0, rpos = 0;
  while (sz0 < arSize && sz1 < usz) {
    if (v[sz0].first.first > u[sz1].first.first) {
      ret[rpos++] = (v[sz0++]);
    } else {
      ret[rpos++] = (u[sz1++]);
    }
  }
  while (sz0 < arSize) {
    ret[rpos++] = (v[sz0++]);
  }
  while (sz1 < usz) {
    ret[rpos++] = (u[sz1++]);
  }
  arSize = rpos;
  for (int i = 0; i < arSize; ++i) {
    v[i] = ret[i];
  }
}
pair<long long, long long> q[300001];
int ttt[300001];
void solve() {
  int n;
  scanf("%d ", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%lld %lld", &type[i], &a[i]);
    if (type[i] == 1) {
      scanf("%lld ", &b[i]);
    }
    out[i] = mini;
  }
  int pos = 0;
  int vsz = 0;
  for (int i = 1; i <= n; i += SQ) {
    int ed = min(n, i + SQ - 1);
    int sz = 0;
    int gsz = 0;
    for (int j = i; j <= ed; ++j) {
      if (type[j] == 2 && a[j] < i) {
        isErased[a[j]] = true;
        int id = a[j];
        g[gsz++] = {{a[id], b[id]}, j};
      }
    }
    int tsz = 0;
    for (int j = 0; j < vsz; ++j) {
      if (!isErased[v[j].second]) {
        v[sz++] = v[j];
      }
    }
    vsz = sz;
    convexSz = 0;
    p = 0;
    for (int j = 0; j < vsz; ++j) {
      insert(v[j].first.first, v[j].first.second);
    }
    int qsz = 0;
    for (int j = i; j <= ed; ++j) {
      q[qsz++] = {a[j], j};
    }
    sort(q, q + qsz);
    if (convexSz > 0)
      for (int j = 0; j < qsz; ++j) {
        out[q[j].second] = query(q[j].first);
      }
    int tttsz = 0;
    for (int j = i; j <= ed; ++j) {
      if (type[j] == 3) {
        for (int k = 0; k < tttsz; ++k) {
          int tid = ttt[k];
          if (!isErased[tid]) out[j] = max(out[j], a[tid] * a[j] + b[tid]);
        }
        for (int k = gsz - 1; k >= 0; --k) {
          if (g[k].second < j) {
            break;
          }
          out[j] = max(out[j], g[k].first.first * a[j] + g[k].first.second);
        }
      } else if (type[j] == 2) {
        isErased[a[j]] = true;
      } else {
        ttt[tttsz++] = j;
      }
    }
    merge(vsz, i, ed);
  }
  for (int i = 1; i <= n; ++i) {
    if (type[i] == 3) {
      if (out[i] != mini)
        printf("%lld\n", out[i]);
      else
        printf("EMPTY SET\n");
    }
  }
}
int main() {
  solve();
  return 0;
}