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 + 10;
const long long INF = -(long long)2e18 - 1;
struct point {
  int x, y;
  point(int x = 0, int y = 0) : x(x), y(y) {}
  long long calc(long long q) { return q * x + y; }
} pt[N];
point operator-(point p, point q) { return point(p.x - q.x, p.y - q.y); }
long long operator*(point p, point q) {
  return (long long)p.x * q.y - (long long)p.y * q.x;
}
bool operator<(point p, point q) {
  if (p.x != q.x) return p.x < q.x;
  return p.y < q.y;
}
vector<point> v[N << 2];
void update(point p, int L, int R, int l, int r, int rt) {
  if (l >= L && r <= R) {
    v[rt].push_back(p);
    return;
  }
  int m = l + r >> 1;
  if (m >= L) update(p, L, R, l, m, rt << 1);
  if (m < R) update(p, L, R, m + 1, r, rt << 1 | 1);
}
int vis[N], q[N];
long long ans[N];
void construct(int rt) {
  sort(v[rt].begin(), v[rt].end());
  if (v[rt].size() < 3) return;
  vector<point>& t = v[rt];
  int i = 1, j = 2, c = 2;
  while (j < t.size()) {
    if (i > 0 && (t[i] - t[i - 1]) * (t[j] - t[i - 1]) >= 0) {
      i--;
      c--;
    } else {
      t[++i] = t[j];
      j++;
      c++;
    }
  }
  t.resize(c);
}
long long search(int q, int rt) {
  vector<point>& t = v[rt];
  int l = 0, r = t.size() - 1, ml, mr;
  while (r - l > 2) {
    int len = (r - l + 1) / 3;
    ml = l + len;
    mr = l + 2 * len;
    if (t[ml].calc(q) < t[mr].calc(q)) {
      l = ml;
    } else {
      r = mr;
    }
  }
  long long mx = INF;
  for (int i = l; i <= r; i++) {
    long long tmp;
    if ((tmp = t[i].calc(q)) > mx) {
      mx = tmp;
    } else
      break;
  }
  return mx;
}
void query(int l, int r, int rt) {
  construct(rt);
  for (int i = l; i <= r; i++) {
    if (vis[i] == 0) {
      ans[i] = max(ans[i], search(q[i], rt));
    }
  }
  if (l == r) return;
  int m = l + r >> 1;
  query(l, m, rt << 1);
  query(m + 1, r, rt << 1 | 1);
}
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    ans[i] = INF;
    int t;
    cin >> t;
    if (t == 1) {
      vis[i] = 2;
      cin >> pt[i].x >> pt[i].y;
    } else if (t == 2) {
      int x;
      cin >> x;
      vis[x] = 1;
      vis[i] = 1;
      update(pt[x], x, i - 1, 1, n, 1);
    } else {
      cin >> q[i];
    }
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i] == 2) {
      update(pt[i], i, n, 1, n, 1);
    }
  }
  query(1, n, 1);
  for (int i = 1; i <= n; i++) {
    if (vis[i] == 0) {
      if (ans[i] == INF)
        cout << "EMPTY SET\n";
      else
        cout << ans[i] << endl;
    }
  }
  return 0;
}