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 T = (1 << 19);
pair<long long int, long long int> val[T];
const long long int INF = 1LL << 61;
bool cmpA;
struct Line {
  long long int a, b;
  mutable long double xl;
  bool operator<(const Line &l) const {
    if (cmpA)
      return a < l.a;
    else
      return xl < l.xl;
  }
};
struct DynamicHull : multiset<Line> {
  bool bad(iterator y) {
    iterator z = next(y), x;
    if (y == begin()) {
      if (z == end()) return 0;
      return y->a == z->a && y->b <= z->b;
    }
    x = prev(y);
    if (z == end()) {
      return y->a == x->a && y->b <= x->b;
    }
    return 1.0L * (x->b - y->b) * (z->a - y->a) >=
           1.0L * (y->b - z->b) * (y->a - x->a);
  }
  void add(long long int a, long long int b) {
    cmpA = 1;
    iterator y = insert((Line){a, b, -INF});
    if (bad(y)) {
      erase(y);
      return;
    }
    while (next(y) != end() && bad(next(y))) erase(next(y));
    while (y != begin() && bad(prev(y))) erase(prev(y));
    if (next(y) != end())
      next(y)->xl = 1.0L * (y->b - next(y)->b) / (next(y)->a - y->a);
    if (y != begin()) y->xl = 1.0L * (y->b - prev(y)->b) / (prev(y)->a - y->a);
  }
  long long int eval(long long int x) {
    if (empty()) return -INF;
    cmpA = 0;
    iterator it = prev(lower_bound((Line){0, 0, 1.0L * x}));
    return it->a * x + it->b;
  }
};
DynamicHull seg[2 * T];
void upd(int root, int lm, int rm, int u, int v,
         pair<long long int, long long int> val) {
  if (u <= lm && rm <= v) {
    seg[root].add(val.first, val.second);
    return;
  }
  int m = (lm + rm) / 2;
  if (u <= m) upd(2 * root, lm, m, u, v, val);
  if (m < v) upd(2 * root + 1, m + 1, rm, u, v, val);
}
long long int que(int pos, long long int val) {
  long long int ans = -INF;
  while (pos) {
    ans = max(ans, seg[pos].eval(val));
    pos /= 2;
  }
  return ans;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    val[i] = pair<long long int, long long int>(-INF, -INF);
  for (int i = 1; i <= n; ++i) {
    int ty;
    scanf("%d", &ty);
    if (ty == 1) {
      int x, y;
      scanf("%d %d", &x, &y);
      val[i] = pair<long long int, long long int>(x, y);
    } else if (ty == 2) {
      int prev;
      scanf("%d", &prev);
      upd(1, T, 2 * T - 1, T + prev, T + i, val[prev]);
      val[prev] = pair<long long int, long long int>(-INF, -INF);
    } else {
      int q;
      scanf("%d", &q);
      val[i] = pair<long long int, long long int>(q, -INF);
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (val[i].second != -INF) {
      upd(1, T, 2 * T - 1, T + i, 2 * T - 1, val[i]);
      val[i] = pair<long long int, long long int>(-INF, -INF);
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (val[i].first != -INF) {
      long long int ans = que(T + i, val[i].first);
      if (ans == -INF)
        printf("EMPTY SET\n");
      else
        printf("%lld\n", ans);
    }
  }
  return 0;
}