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>
struct point {
  int x, y;
} p[300001];
int N, active[300001], right[300001], Q;
int order[300001], L;
struct query {
  int pos, x, id;
} qry[300001], tmp[300001];
long long O[300001];
std::vector<int> T[1048576];
void P(int p, int l, int r, int L, int R, int id) {
  if (L <= l && r <= R) {
    T[p].push_back(id);
    return;
  }
  int m = l + r >> 1;
  if (L <= m) P(p << 1, l, m, L, R, id);
  if (R > m) P(p << 1 | 1, m + 1, r, L, R, id);
}
inline bool cover(const point &a, const point &b, const point &c) {
  return (long long)(b.y - a.y) * (c.x - b.x) <=
         (long long)(c.y - b.y) * (b.x - a.x);
}
void convex_append(int *q, int &D, int x) {
  if (D && p[q[D]].x == p[x].x) {
    if (p[q[D]].y >= p[x].y) return;
    D--;
  }
  while (D > 1 && cover(p[q[D - 1]], p[q[D]], p[x])) D--;
  q[++D] = x;
}
inline long long ans(const query &a, const point &b) {
  return (long long)a.x * b.x + b.y;
}
void I_Love_Little_Fairy_MY(int p, int l, int r, int L, int R) {
  if (l == r)
    std::sort(qry + L, qry + R + 1,
              [](const query &a, const query &b) { return a.x < b.x; });
  else {
    int m = l + r >> 1, curL = L - 1, curR = R + 1;
    for (int i = L; i <= R; i++)
      tmp[qry[i].pos <= m ? ++curL : --curR] = qry[i];
    std::copy(tmp + L, tmp + R + 1, qry + L);
    I_Love_Little_Fairy_MY(p << 1, l, m, L, curL);
    I_Love_Little_Fairy_MY(p << 1 | 1, m + 1, r, curR, R);
    for (int i = L, j = L, k = curR; i <= R; i++)
      tmp[i] =
          qry[(j > curL ? k : (k > R ? j : (qry[j].x <= qry[k].x ? j : k)))++];
    std::copy(tmp + L, tmp + R + 1, qry + L);
  }
  static int q[300001];
  int D = 0;
  for (int e : T[p]) convex_append(q, D, e);
  if (!D) return;
  for (int i = L, j = 1; i <= R; i++) {
    while (j < D && ans(qry[i], ::p[q[j]]) < ans(qry[i], ::p[q[j + 1]])) j++;
    O[qry[i].id] = std::max(O[qry[i].id], ans(qry[i], ::p[q[j]]));
  }
}
int main() {
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    int ty;
    scanf("%d", &ty);
    if (ty == 1) {
      active[i] = 1;
      right[i] = N;
      scanf("%d%d", &p[i].x, &p[i].y);
    } else if (ty == 2) {
      int t;
      scanf("%d", &t);
      right[t] = i;
    } else {
      qry[++Q].pos = i;
      scanf("%d", &qry[Q].x);
      qry[Q].id = Q;
    }
  }
  for (int i = 1; i <= N; i++)
    if (active[i]) order[++L] = i;
  std::sort(order + 1, order + L + 1,
            [](int x, int y) { return p[x].x < p[y].x; });
  for (int i = 1; i <= L; i++) P(1, 1, N, order[i], right[order[i]], order[i]);
  for (int i = 1; i <= Q; i++) O[i] = -1LL << 60;
  I_Love_Little_Fairy_MY(1, 1, N, 1, Q);
  for (int i = 1; i <= Q; i++)
    if (O[i] == -1LL << 60)
      puts("EMPTY SET");
    else
      printf("%lld\n", O[i]);
  return 0;
}