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 edge {
  int u, v;
  long long w;
};
long long MOD = 1000000007;
long long _MOD = 1000000009;
double EPS = 1e-10;
int INF = INT_MAX / 2;
int B = 1000;
bool f(pair<int, int>& p, pair<int, int>& q, pair<int, int>& r) {
  long long dx1 = q.first - p.first, dy1 = q.second - p.second;
  long long dx2 = r.first - q.first, dy2 = r.second - q.second;
  return dx2 * dy1 <= dx1 * dy2;
}
int main() {
  int Q;
  cin >> Q;
  vector<int> t(Q), a(Q), b(Q);
  for (int k = 0; k < Q; k++) {
    scanf("%d", &t[k]);
    if (t[k] == 1) scanf("%d%d", &a[k], &b[k]);
    if (t[k] == 2) {
      scanf("%d", &a[k]);
      a[k]--;
    }
    if (t[k] == 3) scanf("%d", &a[k]);
  }
  vector<int> X;
  for (int k = 0; k < Q; k++)
    if (t[k] == 1) X.push_back(a[k]);
  sort(X.begin(), X.end());
  X.erase(unique(X.begin(), X.end()), X.end());
  int M = X.size();
  vector<int> index(Q);
  for (int k = 0; k < Q; k++)
    if (t[k] == 1) index[k] = lower_bound(X.begin(), X.end(), a[k]) - X.begin();
  vector<bool> rem(Q), yotei(Q);
  for (int l = 0; l < Q; l += B) {
    int r = min(Q, l + B);
    for (int k = l; k < r; k++)
      if (t[k] == 2) yotei[a[k]] = true;
    vector<int> backet(M, -INF), added;
    for (int k = 0; k < l; k++) {
      if (t[k] != 1) continue;
      if (yotei[k]) {
        if (!rem[k]) added.push_back(k);
      } else {
        int i = index[k];
        backet[i] = max(backet[i], b[k]);
      }
    }
    int N = 0;
    vector<pair<int, int> > s;
    for (int i = 0; i < M; i++) {
      if (backet[i] == -INF) continue;
      pair<int, int> p(X[i], backet[i]);
      while (N >= 2 && f(s[N - 2], s[N - 1], p)) {
        N--;
        s.pop_back();
      }
      N++;
      s.push_back(p);
    }
    for (int k = l; k < r; k++) {
      if (t[k] == 1) added.push_back(k);
      if (t[k] == 2) rem[a[k]] = true;
      if (t[k] == 3) {
        long long z = a[k], ans = LLONG_MIN;
        int lb = 0, ub = N - 1;
        while (ub - lb > 1) {
          int mid = (lb + ub) / 2;
          if (s[mid].first * z + s[mid].second <
              s[mid + 1].first * z + s[mid + 1].second)
            lb = mid;
          else
            ub = mid;
        }
        if (lb < N) ans = max(ans, s[lb].first * z + s[lb].second);
        if (lb + 1 < N) ans = max(ans, s[lb + 1].first * z + s[lb + 1].second);
        for (int k : added)
          if (!rem[k]) ans = max(ans, a[k] * z + b[k]);
        if (ans == LLONG_MIN)
          printf("EMPTY SET\n");
        else
          printf("%lld\n", ans);
      }
    }
  }
}