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 int MAXN = 300005;
const int DEL = 1e9 + 7;
const long long INF = 2e18;
struct Line {
  int k, b;
  Line() {}
  Line(int k, int b) : k(k), b(b) {}
  long long f(int x) { return 1LL * k * x + b; }
  bool operator<(const Line& a) const { return k != a.k ? k < a.k : b < a.b; }
};
vector<Line> T[MAXN << 1];
pair<int, int> seg[MAXN], op[MAXN];
int n, cnt;
void add(int L, int R, int k, int b, int l, int r) {
  int o = l + r | (l != r), m = l + r >> 1;
  if (L <= l && r <= R)
    T[o].push_back(Line(k, b));
  else {
    if (L <= m) add(L, R, k, b, l, m);
    if (m < R) add(L, R, k, b, m + 1, r);
  }
}
int check(vector<Line>& a, int i, int j, int k) {
  return 1LL * (a[i].b - a[j].b) * (a[k].k - a[i].k) >=
         1LL * (a[i].b - a[k].b) * (a[j].k - a[i].k);
}
void calc(vector<Line>& T) {
  static int S[MAXN], i, t;
  sort(T.begin(), T.end());
  for (i = 0, t = 0; i < T.size(); ++i) {
    while (t && T[S[t]].k == T[i].k || t > 1 && check(T, S[t - 1], S[t], i))
      --t;
    S[++t] = i;
  }
  vector<Line> nxt;
  for (i = 1; i <= t; ++i) {
    nxt.push_back(T[S[i]]);
  }
  T = nxt;
}
long long get_max_val(int x, int o) {
  if (!T[o].size()) return -INF;
  int l = 0, r = T[o].size() - 1;
  while (l < r) {
    int m = l + r >> 1;
    if (T[o][m].f(x) > T[o][m + 1].f(x))
      r = m;
    else
      l = m + 1;
  }
  return T[o][l].f(x);
}
long long query(int x, int pos, int l, int r) {
  long long res = -INF;
  while (l < r) {
    int o = l + r | (l != r), m = l + r >> 1;
    res = max(res, get_max_val(x, o));
    if (pos <= m)
      r = m;
    else
      l = m + 1;
  }
  res = max(res, get_max_val(x, l + r | (l != r)));
  return res;
}
void solve() {
  cnt = 0;
  for (int i = 1; i <= n << 1; ++i) T[i].clear();
  for (int i = 1, c; i <= n; ++i) {
    scanf("%d%d", &c, &seg[i].first);
    if (c == 1)
      scanf("%d", &seg[i].second);
    else if (c == 2) {
      int x = seg[i].first;
      add(x, i, seg[x].first, seg[x].second, 1, n);
      seg[x].first = seg[i].first = DEL;
    } else
      op[++cnt] = pair<int, int>(seg[i].first, i), seg[i].first = DEL;
  }
  for (int i = 1; i <= n; ++i) {
    if (seg[i].first != DEL) add(i, n, seg[i].first, seg[i].second, 1, n);
  }
  for (int i = 1; i <= n << 1; ++i)
    if (T[i].size()) {
      calc(T[i]);
    }
  for (int i = 1; i <= cnt; ++i) {
    long long res = query(op[i].first, op[i].second, 1, n);
    if (res == -INF)
      printf("EMPTY SET\n");
    else
      printf("%lld\n", res);
  }
}
int main() {
  while (~scanf("%d", &n)) solve();
  return 0;
}