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>
const long long INF = 1LL << 61;
using namespace std;
int t[300005], r[300005], empty[300005];
long long ans[300005];
struct Point {
  long long x, y;
  bool operator<(const Point &B) const {
    return x < B.x || (x == B.x && y < B.y);
  }
  Point operator-(const Point &B) const { return (Point){x - B.x, y - B.y}; }
  Point operator+(const Point &B) const { return (Point){x + B.x, y + B.y}; }
  long long operator^(const Point &B) const { return x * B.y - y * B.x; }
  long long operator*(const Point &B) const { return x * B.x + y * B.y; }
} p[300005], S[300005];
vector<Point> tr[300005 << 2];
void insert(int l, int r, int L, int R, int o, int v) {
  if (l <= L && R <= r) {
    tr[o].push_back(p[v]);
    return;
  }
  int M = L + R >> 1;
  if (l <= M) insert(l, r, L, M, o << 1, v);
  if (r > M) insert(l, r, M + 1, R, o << 1 | 1, v);
}
void query(int x, int n) {
  int l = 1, r = n;
  while (r - l >= 3) {
    int m1 = l + (r - l) / 3;
    int m2 = l + (r - l) * 2 / 3;
    if (p[x] * S[m1] < p[x] * S[m2])
      l = m1;
    else
      r = m2;
  }
  for (int i = l; i <= r; i++) ans[x] = max(ans[x], p[x] * S[i]);
}
void solve(int l, int r, int o) {
  if (l < r) {
    int m = l + r >> 1;
    solve(l, m, o << 1);
    solve(m + 1, r, o << 1 | 1);
  }
  sort(tr[o].begin(), tr[o].end());
  int top = 0;
  for (int i = 0; i < tr[o].size(); i++) {
    while (top > 1 && ((S[top] - S[top - 1]) ^ (tr[o][i] - S[top])) >= 0) top--;
    S[++top] = tr[o][i];
  }
  for (int i = l; i <= r; i++)
    if (t[i] == 3 && !empty[i]) query(i, top);
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1, cnt = 0, x; i <= n; i++) {
    scanf("%d", &t[i]);
    if (t[i] == 1)
      scanf("%lld %lld", &p[i].x, &p[i].y), r[i] = n, cnt++;
    else if (t[i] == 2)
      scanf("%d", &x), r[x] = i, cnt--;
    else
      scanf("%lld", &p[i].x), p[i].y = 1LL, empty[i] = (cnt == 0),
                              ans[i] = -INF;
  }
  for (int i = 1; i <= n; i++)
    if (t[i] == 1 && i + 1 <= r[i]) insert(i, r[i], 1, n, 1, i);
  solve(1, n, 1);
  for (int i = 1; i <= n; i++)
    if (t[i] == 3) {
      if (empty[i])
        puts("EMPTY SET");
      else
        printf("%lld\n", ans[i]);
    }
  return 0;
}