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>
#pragma GCC optimize(3)
#pragma GCC optimize(2)
using namespace std;
const long long inf = 2e18 + 17;
struct line {
  long long m, b;
};
long long floordiv(long long a, long long b) {
  return a / b - (a % b && ((a < 0) ^ (b < 0)));
}
long long intersect(line a, line b) { return floordiv(b.b - a.b, a.m - b.m); }
pair<int, int> org[1048597 >> 1];
pair<pair<int, int>, int> ist[1048597 >> 1];
struct Convex {
  vector<line> cht;
  void insert(line l) {
    auto n = cht.size();
    while ((n >= 1 && l.m == cht[n - 1].m && l.b >= cht[n - 1].b) ||
           (n >= 2 &&
            intersect(cht[n - 1], cht[n - 2]) >= intersect(cht[n - 1], l))) {
      cht.pop_back();
      n = cht.size();
    }
    cht.push_back(l);
  }
  long long query(long long x) {
    if (cht.empty()) return -inf;
    int low = 0, high = (int)cht.size() - 2;
    int ret = (int)cht.size() - 1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (intersect(cht[mid], cht[mid + 1]) >= x) {
        ret = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return cht[ret].m * x + cht[ret].b;
  }
};
Convex tree[1048597];
void update(int start, int end, int l, int r, int index, line li) {
  if (start > end || l > r || start > r || l > end) return;
  if (start <= l && r <= end) {
    tree[index].insert(li);
    return;
  }
  if (end <= ((l + r) >> 1)) {
    update(start, end, l, ((l + r) >> 1), (index << 1), li);
  } else if (start >= ((l + r) >> 1) + 1) {
    update(start, end, ((l + r) >> 1) + 1, r, (index << 1 | 1), li);
  } else {
    update(start, end, l, ((l + r) >> 1), (index << 1), li);
    update(start, end, ((l + r) >> 1) + 1, r, (index << 1 | 1), li);
  }
}
long long query(int pt, int l, int r, int index, long long x) {
  if (pt < l || pt > r || l > r) return -inf;
  long long ret = tree[index].query(x);
  if (l == r) return ret;
  if (pt <= ((l + r) >> 1)) {
    ret = max(ret, query(pt, l, ((l + r) >> 1), (index << 1), x));
  } else {
    ret = max(ret, query(pt, ((l + r) >> 1) + 1, r, (index << 1 | 1), x));
  }
  return ret;
}
struct event {
  int from, to, tp;
  int a, b;
};
event evt[1048597 >> 1];
vector<pair<pair<int, int>, pair<int, int>>> add;
int main() {
  int i, n;
  scanf("%d", &n);
  for (i = 1; i <= n; ++i) {
    scanf("%d", &evt[i].tp);
    if (evt[i].tp == 1) {
      scanf("%d%d", &evt[i].a, &evt[i].b);
      evt[i].from = i;
    } else if (evt[i].tp == 2) {
      int x;
      scanf("%d", &x);
      evt[x].to = i;
    } else {
      scanf("%d", &evt[i].b);
    }
  }
  for (i = 1; i <= n; ++i) {
    if (evt[i].tp == 1 && evt[i].from != 0 && evt[i].to == 0) {
      evt[i].to = n;
    }
  }
  for (i = 1; i <= n; ++i) {
    if (evt[i].tp == 1) {
      add.push_back(make_pair(make_pair(evt[i].a, evt[i].b),
                              make_pair(evt[i].from, evt[i].to)));
    }
  }
  sort(add.begin(), add.end());
  for (auto &e : add) {
    line li = line{e.first.first, e.first.second};
    update(e.second.first, e.second.second, 1, n, 1, li);
  }
  for (i = 1; i <= n; ++i) {
    if (evt[i].tp == 3) {
      long long ret = query(i, 1, n, 1, evt[i].b);
      if (ret <= -inf) {
        printf("EMPTY SET\n");
      } else {
        printf("%I64d\n", ret);
      }
    }
  }
  return 0;
}