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 long long inf = 1e18 + 2e9;
struct query {
  int flag, x, y, id;
};
query qy[300100];
struct point {
  int x, y;
  double ix, iy;
  bool operator<(const point &temp) const {
    if (x == temp.x) return y > temp.y;
    return x < temp.x;
  }
};
point now, stk[300100];
vector<point> vec[1 << 20];
bool del[300100];
int n, top;
long long ans[300100];
void insert(int left, int right, int ql, int qr, int ip, int id) {
  int l = 2 * id + 1, r = 2 * id + 2, mid = (left + right) >> 1;
  if (left > qr || right < ql) return;
  if (ql <= left && right <= qr) {
    now.x = qy[ip].x;
    now.y = qy[ip].y;
    vec[id].push_back(now);
    return;
  }
  insert(left, mid, ql, qr, ip, l);
  insert(mid + 1, right, ql, qr, ip, r);
}
void solve(int left, int right, int id) {
  int i, j, s, p, q, mid = (left + right) >> 1, l = 2 * id + 1, r = 2 * id + 2,
                     low, high;
  if (left < right) {
    solve(left, mid, l);
    solve(mid + 1, right, r);
  }
  sort(vec[id].begin(), vec[id].end());
  top = 0;
  for (i = 0; i < vec[id].size(); i++) {
    if (i == 0 || vec[id][i].x != vec[id][i - 1].x) stk[top++] = vec[id][i];
  }
  for (i = 0; i < top; i++) vec[id][i] = stk[i];
  while (vec[id].size() > top) vec[id].pop_back();
  top = 0;
  for (i = 0; i < vec[id].size(); i++) {
    while (top >= 2) {
      if ((double)vec[id][i].x * stk[top - 2].ix + vec[id][i].y >=
          stk[top - 2].iy)
        top--;
      else
        break;
    }
    if (top >= 1) {
      stk[top - 1].ix = (double)(vec[id][i].y - stk[top - 1].y) /
                        (double)(stk[top - 1].x - vec[id][i].x);
      stk[top - 1].iy = vec[id][i].x * stk[top - 1].ix + vec[id][i].y;
    }
    stk[top++] = vec[id][i];
  }
  if (top == 0) return;
  for (i = left; i <= right; i++) {
    if (qy[i].flag == 3) {
      int low, high, mid;
      low = 0;
      high = top - 2;
      while (low <= high) {
        mid = (low + high) >> 1;
        if (stk[mid].ix < qy[i].x)
          low = mid + 1;
        else
          high = mid - 1;
      }
      long long vl =
          (long long)stk[low].x * (long long)qy[i].x + (long long)stk[low].y;
      if (ans[i] < vl) ans[i] = vl;
    }
  }
}
int main() {
  int i, j, s, p, q;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &qy[i].flag);
    if (qy[i].flag == 1)
      scanf("%d%d", &qy[i].x, &qy[i].y);
    else if (qy[i].flag == 2) {
      scanf("%d", &qy[i].id);
      del[qy[i].id] = true;
      insert(1, n, qy[i].id, i, qy[i].id, 0);
    } else if (qy[i].flag == 3)
      scanf("%d", &qy[i].x);
  }
  for (i = 1; i <= n; i++) {
    if (qy[i].flag == 1 && !del[i]) insert(1, n, i, n, i, 0);
  }
  for (i = 1; i <= n; i++) ans[i] = -inf;
  solve(1, n, 0);
  for (i = 1; i <= n; i++) {
    if (qy[i].flag == 3) {
      if (ans[i] == -inf)
        puts("EMPTY SET");
      else
        printf("%I64d\n", ans[i]);
    }
  }
}