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 Node {
  long long x, y;
  Node(int a = 0, int b = 0) { x = a, y = b; }
  bool operator<(const Node &b) const {
    if (x == b.x)
      return y < b.y;
    else
      return x < b.x;
  }
  Node operator-(const Node &b) const { return Node(x - b.x, y - b.y); }
  long long operator*(const Node &b) const { return x * b.y - y * b.x; }
} v[300005];
long long ans;
int n, x, opt[300005], q[300005], End[300005];
vector<Node> t[1200005];
void update(int o, int l, int r, int x, int y, Node v) {
  if (x <= l && y >= r) {
    t[o].push_back(v);
  } else {
    int mid = l + r >> 1;
    if (x <= mid) update((o << 1), l, mid, x, y, v);
    if (y >= mid + 1) update((o << 1 | 1), mid + 1, r, x, y, v);
  }
}
void dfs(int o, int l, int r) {
  vector<Node> &v = t[o];
  if (!v.empty()) sort(v.begin(), v.end());
  if (v.size() > 2) {
    int i, j;
    for (i = 2, j = 1; i < v.size(); i++) {
      while (j > 0 && (v[j] - v[j - 1]) * (v[i] - v[j - 1]) >= 0) j--;
      v[++j] = v[i];
    }
    while (v.size() > j + 1) v.pop_back();
  }
  if (r == l) return;
  int mid = l + r >> 1;
  dfs((o << 1), l, mid), dfs((o << 1 | 1), mid + 1, r);
}
long long solve(vector<Node> &v, long long q) {
  long long ans = -2e18;
  int l = 0, r = v.size() - 1;
  while (r - l > 6) {
    int mid1 = (l * 2 + r) / 3;
    int mid2 = (l + r * 2) / 3;
    if (v[mid1].x * q + v[mid1].y > v[mid2].x * q + v[mid2].y)
      r = mid2;
    else
      l = mid1;
  }
  for (int i = l; i <= r; i++) ans = max(ans, v[i].x * q + v[i].y);
  return ans;
}
void query(int o, int l, int r, int x, int q) {
  ans = max(ans, solve(t[o], q));
  if (r == l) return;
  int mid = l + r >> 1;
  if (x <= mid)
    query((o << 1), l, mid, x, q);
  else
    query((o << 1 | 1), mid + 1, r, x, q);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", opt + i);
    if (opt[i] == 1) {
      scanf("%lld%lld", &v[i].x, &v[i].y);
      End[i] = n;
    } else if (opt[i] == 2) {
      scanf("%d", &x);
      End[x] = i - 1;
    } else if (opt[i] == 3) {
      scanf("%d", q + i);
    }
  }
  for (int i = 1; i <= n; i++)
    if (opt[i] == 1) update(1, 1, n, i, End[i], v[i]);
  dfs(1, 1, n);
  for (int i = 1; i <= n; i++) {
    if (opt[i] == 3) {
      ans = -2e18;
      query(1, 1, n, i, q[i]);
      if (ans <= -2e18)
        printf("EMPTY SET\n");
      else
        printf("%lld\n", ans);
    }
  }
  return 0;
}