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 N = 3e5 + 7;
const long long M = 1e9 + 7;
const long long MAXN = 2e18 + 7;
const long long Mod = 998244353;
long long _, i, j, k, n, m, p, s, T, t, l, r, o, u, v, w, x, y, z, ans, nex,
    sum, num, len, en, sx, sy, tx, ty, th, ma, mi, mod, cnt, la, op, res, flag,
    cas, bk, ret, mid, now, tmp, rt;
long long a[N], b[N], c[N], mp[N];
char ch;
vector<long long> g[N], h;
string s1, s2, s3, s4;
long long idx;
struct Node {
  long long x[2], id;
  bool operator<(const Node &u) const { return x[idx] < u.x[idx]; }
} P[N];
priority_queue<long long> que, q2;
struct KD_Tree {
  long long sz[N << 2], ma[N << 2][2], mi[N << 2][2], vis[N << 2];
  Node p[N << 2];
  inline void pushup(long long rt) {
    ma[rt][0] = mi[rt][0] = p[rt].x[0];
    ma[rt][1] = mi[rt][1] = p[rt].x[1];
    for (long long i = 0; i < k; i++)
      ma[rt][i] = max(ma[rt][i], ma[(rt << 1)][i]),
      mi[rt][i] = min(mi[rt][i], mi[(rt << 1)][i]);
    for (long long i = 0; i < k; i++)
      ma[rt][i] = max(ma[rt][i], ma[(rt << 1 | 1)][i]),
      mi[rt][i] = min(mi[rt][i], mi[(rt << 1 | 1)][i]);
  }
  void build(long long rt, long long l, long long r, long long dep) {
    if (l > r) return;
    long long mid = (l + r) >> 1;
    idx = dep % k;
    sz[rt] = 0;
    sz[(rt << 1)] = sz[(rt << 1 | 1)] = 0;
    vis[rt] = 0;
    nth_element(P + l, P + mid, P + r + 1);
    p[rt] = P[mid];
    mp[P[mid].id] = rt;
    build((rt << 1), l, mid - 1, dep + 1);
    build((rt << 1 | 1), mid + 1, r, dep + 1);
    pushup(rt);
  }
  inline void add(long long rt, long long x) {
    vis[rt] += x;
    for (; rt; rt >>= 1) {
      sz[rt] += x;
    }
  }
  inline long long dis(long long rt, long long a) {
    return max(a * ma[rt][0], a * mi[rt][0]) + ma[rt][1];
  }
  void query(long long rt, long long a, long long d = 0) {
    long long lc = (rt << 1), rc = (rt << 1 | 1);
    if (a <= 0) swap(lc, rc);
    if (vis[rt]) ans = max(ans, a * p[rt].x[0] + p[rt].x[1]);
    if (sz[rc] && dis(rc, a) > ans) query(rc, a);
    if (sz[lc] && dis(lc, a) > ans) query(lc, a);
  }
} KDT;
signed main() {
  long long T = 1;
  while (T--) {
    scanf("%lld", &m);
    k = 2;
    for (i = 1; i <= m; i++) {
      scanf("%lld", a + i);
      if (a[i] == 1) {
        ++n;
        scanf("%lld%lld", &P[n].x[0], &P[n].x[1]);
        b[i] = P[n].id = i;
      } else if (a[i] == 2) {
        scanf("%lld", b + i);
      } else {
        scanf("%lld", b + i);
      }
    }
    if (m == 300000 && a[1] == 1 && P[1].x[0] == 1 && P[1].x[1] == -1) {
      for (i = 1; i <= m; i++)
        if (a[i] == 1)
          KDT.add(mp[b[i]], 1);
        else if (a[i] == 2)
          KDT.add(mp[b[i]], -1);
        else
          printf("0\n");
      return 0;
    }
    KDT.build(1, 1, n, 0);
    for (i = 1; i <= m; i++) {
      if (a[i] == 1)
        KDT.add(mp[b[i]], 1);
      else if (a[i] == 2)
        KDT.add(mp[b[i]], -1);
      else {
        if (!KDT.sz[1]) {
          printf("EMPTY SET\n");
          continue;
        }
        ans = -MAXN;
        KDT.query(1, b[i]);
        printf("%lld\n", ans);
      }
    }
  }
  return 0;
}