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 N = 3e5 + 50;
int n, cnt, x[N], y[N], s[N], t[N], q[N], m, p[N], L[N * 4], R[N * 4], tt[N],
    num;
long long d, ans[N];
vector<int> v[N * 4];
bool cmp(int a, int b) { return x[a] < x[b]; }
bool cmpp(int a, int b) { return q[a] < q[b]; }
bool cmp1(int a, int b, int c) {
  int x1 = x[b] - x[a], x2 = x[c] - x[b], y1 = y[b] - y[a], y2 = y[c] - y[b];
  return 1ll * y1 * x2 <= 1ll * y2 * x1;
}
bool cmp2(int a, int b, int k) {
  return y[b] - y[a] >= 1ll * (x[b] - x[a]) * k;
}
long long calc(int a, int q) { return 1ll * x[a] * q + y[a]; }
void change(int x, int l, int r, int ql, int qr, int id) {
  if (l >= ql && r <= qr) {
    while (L[x] + 1 <= R[x] && cmp1(v[x][R[x] - 1], v[x][R[x]], id))
      R[x]--, v[x].pop_back();
    R[x]++;
    v[x].push_back(id);
    return;
  }
  int mid = (l + r) >> 1;
  if (ql <= mid) change(x << 1, l, mid, ql, qr, id);
  if (qr > mid) change(x << 1 | 1, mid + 1, r, ql, qr, id);
}
void query(int x, int l, int r, int p, int k) {
  while (L[x] + 1 <= R[x] && cmp2(v[x][L[x]], v[x][L[x] + 1], k)) L[x]++;
  if (L[x] <= R[x]) d = max(d, calc(v[x][L[x]], -k));
  if (l == r) return;
  int mid = (l + r) >> 1;
  p <= mid ? query(x << 1, l, mid, p, k) : query(x << 1 | 1, mid + 1, r, p, k);
}
int main() {
  scanf("%d", &n);
  for (int i = 1, op, id; i <= n; i++) {
    scanf("%d", &op);
    if (op == 1)
      scanf("%d%d", &x[i], &y[i]), s[i] = i;
    else
      x[i] = 1e9 + 1;
    if (op == 2) scanf("%d", &id), t[id] = i - 1;
    if (op == 3) scanf("%d", &q[++m]), tt[m] = i;
  }
  for (int i = 1; i <= n; i++)
    if (x[i] <= 1e9 && !t[i]) t[i] = n;
  for (int i = 1; i <= n; i++) p[i] = i;
  sort(p + 1, p + n + 1, cmp);
  for (int i = 1; i <= n * 4; i++) R[i] = -1;
  for (int i = 1; i <= n; i++)
    if (x[p[i]] <= 1e9) change(1, 1, n, s[p[i]], t[p[i]], p[i]);
  for (int i = 1; i <= m; i++) p[i] = i;
  sort(p + 1, p + m + 1, cmpp);
  for (int i = 1; i <= m; i++) {
    d = -2e18;
    query(1, 1, n, tt[p[i]], -q[p[i]]);
    ans[p[i]] = d;
  }
  for (int i = 1; i <= m; i++) {
    if (ans[i] == -2e18)
      puts("EMPTY SET");
    else
      cout << ans[i] << endl;
  }
  return 0;
}