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 query {
  int t, a, b;
  query() { t = a = b = 0; }
  query(int t, int a, int b) : t(t), a(a), b(b) {}
  bool operator<(const query& B) const {
    if (a == B.a) return b < B.b;
    return a < B.a;
  }
};
query T[300005];
vector<query> lines;
vector<pair<int, int> > E;
bool active[300005];
bool del[300005];
long long ans[300005];
long long inf = 2e18;
double intersection(pair<int, int> A, pair<int, int>& B) {
  return 1.0 * (B.second - A.second) / (A.first - B.first);
}
long long f(pair<int, int>& A, query& B) {
  return 1ll * A.first * B.a + A.second;
}
long long f(query& A, query& B) { return 1ll * A.a * B.a + A.b; }
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) ans[i] = -inf;
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &T[i].t, &T[i].a);
    if (T[i].t == 1) {
      scanf("%d", &T[i].b);
      lines.push_back(query(i, T[i].a, T[i].b));
    } else if (T[i].t == 2)
      T[i].a--;
  }
  sort(lines.begin(), lines.end());
  int d = sqrt(n);
  for (int l = 0; l < n; l += d) {
    int r = min(n, l + d);
    for (int i = l; i < r; i++)
      if (T[i].t == 2) del[T[i].a] = true;
    E.clear();
    for (int i = 0; i < lines.size(); i++) {
      if (!active[lines[i].t] or del[lines[i].t]) continue;
      while (
          (E.size() > 0 and E.back().first == lines[i].a) or
          (E.size() > 1 and intersection(E[E.size() - 2], E.back()) >
                                intersection(make_pair(lines[i].a, lines[i].b),
                                             E[E.size() - 2])))
        E.pop_back();
      E.push_back(make_pair(lines[i].a, lines[i].b));
    }
    vector<pair<query, int> > Q;
    for (int i = l; i < r; i++)
      if (T[i].t == 3) Q.push_back(make_pair(T[i], i));
    sort(Q.begin(), Q.end());
    int p = 0;
    for (int i = 0; i < Q.size(); i++) {
      while (p + 1 < E.size() and
             f(E[p], Q[i].first) <= f(E[p + 1], Q[i].first))
        p++;
      if (!E.empty()) ans[Q[i].second] = f(E[p], Q[i].first);
    }
    for (int i = l; i < r; i++) {
      if (T[i].t == 1)
        active[i] = 1;
      else if (T[i].t == 2)
        active[T[i].a] = 0;
      else {
        for (int j = l; j < r; j++) {
          if (T[j].t == 1 and active[j])
            ans[i] = max(ans[i], f(T[j], T[i]));
          else if (T[j].t == 2 and active[T[j].a])
            ans[i] = max(ans[i], f(T[T[j].a], T[i]));
        }
        if (ans[i] > -inf)
          printf("%I64d\n", ans[i]);
        else
          puts("EMPTY SET");
      }
    }
  }
  return 0;
}