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 Po {
  long long x, y;
} s[300010], t[300010];
struct PP {
  int l, r;
  Po p;
} p[300010];
struct QQ {
  int t, id;
  long long x;
} q[300010];
long long ans[300010];
int Top, ty[300010], ed[300010];
bool operator<(Po a, Po b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
Po operator-(Po a, Po b) { return (Po){a.x - b.x, a.y - b.y}; }
long long cross(Po a, Po b) { return a.x * b.y - a.y * b.x; }
void tubao(int n) {
  sort(s + 1, s + n + 1);
  Top = 0;
  for (int i = 1; i <= n; i++) {
    while (Top > 1 && cross(t[Top] - t[Top - 1], s[i] - t[Top - 1]) >= 0) Top--;
    t[++Top] = s[i];
  }
}
long long cal(long long x, Po p) { return p.x * x + p.y; }
long long calc(long long x) {
  int l = 1, r = Top;
  while (r - l > 5) {
    int mid_l = l + (r - l + 1) / 3, mid_r = r - (r - l + 1) / 3;
    if (cal(x, t[mid_l]) > cal(x, t[mid_r]))
      r = mid_r;
    else
      l = mid_l;
  }
  long long ans = -2000000000000000000ll;
  for (int i = l; i <= r; i++) ans = max(ans, cal(x, t[i]));
  return ans;
}
void solve(int n, int m, int l, int r) {
  if (!n || !m || l > r) return;
  int w = 0;
  for (int i = 1; i <= n; i++)
    if (p[i].l <= l && r <= p[i].r) s[++w] = p[i].p;
  tubao(w);
  for (int i = 1; i <= m; i++) ans[q[i].id] = max(ans[q[i].id], calc(q[i].x));
  if (l == r) return;
  int mid = (l + r) >> 1;
  int w1 = 0, w2 = 0;
  for (int i = 1; i <= n; i++)
    if (p[i].l <= mid && !(p[i].l <= l && r <= p[i].r)) swap(p[++w1], p[i]);
  for (int i = 1; i <= m; i++)
    if (q[i].t <= mid) swap(q[++w2], q[i]);
  solve(w1, w2, l, mid);
  w1 = 0;
  w2 = 0;
  for (int i = 1; i <= n; i++)
    if (p[i].r > mid && !(p[i].l <= l && r <= p[i].r)) swap(p[++w1], p[i]);
  for (int i = 1; i <= m; i++)
    if (q[i].t > mid) swap(q[++w2], q[i]);
  solve(w1, w2, mid + 1, r);
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &ty[i]);
    if (ty[i] == 1) {
      scanf("%I64d%I64d", &s[i].x, &s[i].y);
      ed[i] = n;
    } else if (ty[i] == 2) {
      int x;
      scanf("%d", &x);
      ed[x] = i;
    } else
      scanf("%I64d", &s[i].x);
  }
  int w1 = 0, w2 = 0;
  for (int i = 1; i <= n; i++)
    if (ty[i] == 1)
      p[++w1] = (PP){i, ed[i], s[i]};
    else if (ty[i] == 3)
      w2++, q[w2] = (QQ){i, w2, s[i].x}, ans[w2] = -2000000000000000000ll;
  solve(w1, w2, 1, n);
  for (int i = 1; i <= w2; i++)
    if (ans[i] != -2000000000000000000ll)
      printf("%I64d\n", ans[i]);
    else
      printf("EMPTY SET\n");
  return 0;
}