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 M = 3e5 + 7;
const int N = 1048583;
const long long INF = 9187201950435737472;
inline int ri() {
  int x = 0;
  bool f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = 0;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
  return f ? x : -x;
}
int n;
long long ans[M];
struct node {
  int x, y;
  node(int _x = 0, int _y = 0) { x = _x, y = _y; }
};
namespace hpi {
struct line {
  long long k, b;
  line(long long _k = 0, long long _b = 0) { k = _k, b = _b; }
  friend bool operator<(const line &x, const line &y) {
    if (x.k != y.k) return x.k < y.k;
    return x.b > y.b;
  }
} p[M], s[M];
int Top, tt;
bool ok(line x, line y, long long ps) {
  return ps * (y.k - x.k) <= (x.b - y.b);
}
long long find(long long x) {
  int l = 1, r = Top, mid;
  while (l < r) {
    mid = l + r >> 1;
    if (mid == Top || ok(s[mid], s[mid + 1], x))
      r = mid;
    else
      l = mid + 1;
  }
  return s[l].k * x + s[l].b;
}
bool chk(line x, line y, line z) {
  return (x.b - z.b) * (y.k - x.k) <= (x.b - y.b) * (z.k - x.k);
}
void build() {
  sort(p + 1, p + tt + 1);
  p[0].k = p[1].k - 1;
  for (int i = 1; i <= tt; i++) {
    if (p[i].k == p[i - 1].k) continue;
    while (Top >= 2 && chk(s[Top - 1], s[Top], p[i])) Top--;
    s[++Top] = p[i];
  }
}
void init() { Top = tt = 0; }
void ins(node d) { p[++tt] = line(d.x, d.y); }
void get(node d) { ans[d.y] = max(ans[d.y], find(d.x)); }
}  // namespace hpi
namespace Seg {
vector<node> p[N], q[N];
void addq(int x, int l, int r, int to, node d) {
  q[x].push_back(d);
  if (l == r) return;
  int mid = l + r >> 1;
  if (to <= mid)
    addq(x << 1, l, mid, to, d);
  else
    addq(x << 1 | 1, mid + 1, r, to, d);
}
void addp(int x, int l, int r, int tl, int tr, node d) {
  if (tl <= l && r <= tr) {
    p[x].push_back(d);
    return;
  }
  int mid = l + r >> 1;
  if (tl <= mid) addp(x << 1, l, mid, tl, tr, d);
  if (mid < tr) addp(x << 1 | 1, mid + 1, r, tl, tr, d);
}
void calc(int x) {
  if (p[x].empty() || q[x].empty()) return;
  int i;
  hpi::init();
  for (i = 0; i < p[x].size(); i++) hpi::ins(p[x][i]);
  hpi::build();
  for (i = 0; i < q[x].size(); i++) hpi::get(q[x][i]);
}
void solve(int x, int l, int r) {
  calc(x);
  if (l == r) return;
  int mid = l + r >> 1;
  solve(x << 1, l, mid);
  solve(x << 1 | 1, mid + 1, r);
}
void addq(int to, node d) { addq(1, 1, n, to, d); }
void addp(int tl, int tr, node d) { addp(1, 1, n, tl, tr, d); }
void solve() { solve(1, 1, n); }
}  // namespace Seg
node a[M];
int tt, tq;
int id[M], bg[M], ed[M];
int main() {
  int i, kd, x, y;
  n = ri();
  for (i = 1; i <= n; i++) {
    kd = ri();
    if (kd == 1) {
      x = ri(), y = ri();
      a[++tt] = node(x, y);
      id[i] = tt;
      bg[tt] = i;
      ed[tt] = n;
    } else if (kd == 2) {
      x = ri();
      ed[id[x]] = i - 1;
    } else {
      x = ri();
      tq++;
      Seg::addq(i, node(x, tq));
    }
  }
  for (i = 1; i <= tt; i++) Seg::addp(bg[i], ed[i], a[i]);
  memset(ans, 128, sizeof ans);
  Seg::solve();
  for (i = 1; i <= tq; i++)
    if (ans[i] == -INF)
      puts("EMPTY SET");
    else
      printf("%I64d\n", ans[i]);
  return 0;
}