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 yts {
  long long x, y;
} st[300010];
bool operator<(yts x, yts y) { return x.x < y.x || (x.x == y.x && x.y < y.y); }
yts operator+(yts x, yts y) { return (yts){x.x + y.x, x.y + y.y}; }
yts operator-(yts x, yts y) { return (yts){x.x - y.x, x.y - y.y}; }
long double operator*(yts x, yts y) {
  return (long double)x.x * y.y - x.y * y.x;
}
vector<yts> t[4 * 300010];
struct yts2 {
  int op;
  long long x, y;
  int T;
} q[300010];
int n, top;
bool vis[300010];
long long ans[300010];
void modify(int i, int l, int r, int L, int R, yts x) {
  if (L <= l && r <= R) {
    t[i].push_back(x);
    return;
  }
  int mid = (l + r) / 2;
  if (L <= mid) modify(i << 1, l, mid, L, R, x);
  if (mid < R) modify(i << 1 | 1, mid + 1, r, L, R, x);
}
long long calc(int i, long long x) { return st[i].x * x + st[i].y; }
long long query(long long x) {
  int l = 1, r = top;
  long long ans = -2e18;
  while (r - l >= 3) {
    int mid = l + (r - l) / 3, midmid = r - (r - l) / 3;
    if (calc(mid, x) > calc(midmid, x))
      r = midmid;
    else
      l = mid;
  }
  for (int i = l; i <= r; i++) ans = max(ans, calc(i, x));
  return ans;
}
void solve(int i, int l, int r) {
  int mid = (l + r) / 2;
  if (l < r) solve(i << 1, l, mid), solve(i << 1 | 1, mid + 1, r);
  if (t[i].size() == 0) return;
  top = 0;
  sort(t[i].begin(), t[i].end());
  for (int j = 0; j < t[i].size(); j++) {
    while (top > 1 && (t[i][j] - st[top]) * (st[top] - st[top - 1]) <= 0) top--;
    st[++top] = t[i][j];
  }
  for (int j = l; j <= r; j++)
    if (q[j].op == 3) ans[j] = max(ans[j], query(q[j].x));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &q[i].op);
    if (q[i].op == 1)
      scanf("%I64d%I64d", &q[i].x, &q[i].y);
    else if (q[i].op == 2) {
      scanf("%d", &q[i].T);
      vis[q[i].T] = 1;
      modify(1, 1, n, q[i].T, i, (yts){q[q[i].T].x, q[q[i].T].y});
    } else if (q[i].op == 3)
      scanf("%I64d", &q[i].x);
  }
  for (int i = 1; i <= n; i++)
    if (q[i].op == 1 && !vis[i]) modify(1, 1, n, i, n, (yts){q[i].x, q[i].y});
  for (int i = 1; i <= n; i++) ans[i] = -2e18;
  solve(1, 1, n);
  for (int i = 1; i <= n; i++)
    if (q[i].op == 3) {
      if (ans[i] != -2e18)
        printf("%I64d\n", ans[i]);
      else
        printf("EMPTY SET\n");
    }
  return 0;
}