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;
struct node {
  long long x, y;
  node(long long X = 0, long long Y = 0) : x(X), y(Y) {}
  node operator+(node a) { return node(x + a.x, y + a.y); }
  node operator-(node a) { return node(x - a.x, y - a.y); }
  long long operator*(node a) { return x * a.y - y * a.x; }
  bool operator<(const node a) const { return x == a.x ? y < a.y : x < a.x; }
};
long long cross(node a, node o, node b) { return (a - o) * (b - o); }
node tmp[300010];
long long calc(node a, long long k) { return a.x * k + a.y; }
struct convex {
  vector<node> v;
  int pos;
  void push(node a) { v.push_back(a); }
  void init() {
    sort(v.begin(), v.end());
    int t = 0;
    pos = 0;
    for (node u : v) {
      while (t > 1 && cross(tmp[t - 1], tmp[t], u) <= 0) --t;
      tmp[++t] = u;
    }
    v.clear();
    for (int i = 1; i <= t; i++) v.push_back(tmp[i]);
  }
  long long answer(long long k) {
    if (v.empty()) return -2000000000000000000;
    if (pos + 1 == v.size()) return calc(v[pos], k);
    while (pos + 1 < v.size() && calc(v[pos], k) <= calc(v[pos + 1], k)) pos++;
    return calc(v[pos], k);
  }
} t[300010 << 2];
void insert(int u, int l, int r, int L, int R, node v) {
  if (L <= l && r <= R) {
    t[u].push(v);
    return;
  }
  int mid = (l + r) >> 1;
  if (L <= mid) insert(u << 1, l, mid, L, R, v);
  if (R > mid) insert(u << 1 | 1, mid + 1, r, L, R, v);
}
long long answer(int u, int l, int r, int p, long long v) {
  long long ans = t[u].answer(v);
  if (l == r) return ans;
  int mid = (l + r) >> 1;
  if (p <= mid)
    return max(ans, answer(u << 1, l, mid, p, v));
  else
    return max(ans, answer(u << 1 | 1, mid + 1, r, p, v));
}
struct ques {
  int p;
  long long k, ans;
  bool operator<(const ques a) const { return k < a.k; }
} q[300010];
bool cmp(ques a, ques b) { return a.p < b.p; }
int qt = 0;
node rem[300010];
bool has[300010];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int opt;
    long long x, y;
    scanf("%d%lld", &opt, &x);
    if (opt == 1) {
      scanf("%lld", &y);
      rem[i] = node(x, y);
      has[i] = true;
    } else if (opt == 2)
      insert(1, 1, n, x, i, rem[x]), has[x] = false;
    else
      q[++qt] = (ques){i, x};
  }
  for (int i = 1; i <= n; i++)
    if (has[i]) insert(1, 1, n, i, n, rem[i]);
  for (int i = 1; i <= 2 * n - 1; i++) t[i].init();
  sort(q + 1, q + qt + 1);
  for (int i = 1; i <= qt; i++) q[i].ans = answer(1, 1, n, q[i].p, q[i].k);
  sort(q + 1, q + qt + 1, cmp);
  for (int i = 1; i <= qt; i++)
    if (q[i].ans <= -2000000000000000000)
      puts("EMPTY SET");
    else
      printf("%lld\n", q[i].ans);
  return 0;
}