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 N = 300005;
struct Point {
  int x, y;
  Point(int _x = 0, int _y = 0) {
    x = _x;
    y = _y;
  }
  Point operator-(const Point &R) const { return Point(x - R.x, y - R.y); }
  long long operator^(const Point &R) const {
    return (long long)x * R.y - (long long)y * R.x;
  }
  long long operator%(const Point &R) const {
    return (long long)x * R.x + (long long)y * R.y;
  }
  bool operator<(const Point &R) const {
    if (x != R.x) return x < R.x;
    return y < R.y;
  }
};
int n, m, p;
Point W[N], K[N];
map<Point, int> Hash;
long long res[N], ans[N];
int a[N];
bool cmpP(const int &A, const int &B) { return W[A] < W[B]; }
bool cmpQ(const int &A, const int &B) {
  return (long long)K[A].x * K[B].y < (long long)K[B].x * K[A].y;
}
void update(vector<int> &P, vector<int> &Q) {
  if (P.empty() || Q.empty()) return;
  sort(P.begin(), P.end(), cmpP);
  vector<int> A, B;
  for (int i = 0; i < Q.size(); ++i)
    if (K[Q[i]].y >= 0) {
      A.push_back(Q[i]);
    }
  sort(A.begin(), A.end(), cmpQ);
  vector<Point> s(P.size() + 1);
  int t = 0;
  for (int i = 0; i < P.size(); ++i) {
    Point D = W[P[i]];
    while (t > 1 && ((D - s[t - 2]) ^ (s[t - 1] - s[t - 2])) <= 0) --t;
    s[t++] = D;
  }
  for (int i = 0, j = 0; i < A.size(); ++i) {
    while (j + 1 < t && (K[A[i]] % s[j + 1]) >= (K[A[i]] % s[j])) ++j;
    res[A[i]] = max(res[A[i]], K[A[i]] % s[j]);
  }
  t = 0;
  for (int i = 0; i < P.size(); ++i) {
    Point D = W[P[i]];
    while (t > 1 && ((D - s[t - 2]) ^ (s[t - 1] - s[t - 2])) >= 0) --t;
    s[t++] = D;
  }
  reverse(A.begin(), A.end());
  for (int i = 0, j = 0; i < A.size(); ++i) {
    while (j + 1 < t && (K[A[i]] % s[j + 1]) >= (K[A[i]] % s[j])) ++j;
    res[A[i]] = max(res[A[i]], K[A[i]] % s[j]);
  }
}
int del[N];
void divide(const vector<int> &A) {
  if (A.size() <= 1) return;
  vector<int> P, Q;
  int r = A.size(), mid = r / 2;
  for (int i = 0; i < mid; ++i) P.push_back(A[i]);
  divide(P);
  P.clear();
  for (int i = 0; i < r; ++i)
    if (A[i] > 0 && (A[i] & 1)) del[A[i] >> 1] = 1;
  for (int i = 0; i < mid; ++i)
    if (A[i] > 0 && (~A[i] & 1)) {
      if (!del[A[i] >> 1])
        P.push_back(A[i] >> 1);
      else
        del[A[i] >> 1] = 2;
    }
  for (int i = mid; i < r; ++i)
    if (A[i] < 0) Q.push_back(-A[i]);
  update(P, Q);
  Q.clear();
  int c1 = 0, c2 = 0;
  for (int i = r - 1; i >= mid; --i) {
    if (A[i] > 0 && (A[i] & 1) && del[A[i] >> 1] == 2) {
      Q.push_back(A[i] ^ 1);
      ++c1;
    } else if (A[i] < 0) {
      Q.push_back(A[i]);
      ++c2;
    }
  }
  for (int i = 0; i < r; ++i)
    if (A[i] > 0 && (A[i] & 1)) del[A[i] >> 1] = 0;
  if (c1 && c2) divide(Q);
  P.clear();
  for (int i = mid; i < r; ++i) P.push_back(A[i]);
  divide(P);
}
int iid[N];
void work() {
  scanf("%d", &n);
  vector<int> A;
  for (int i = 0; i < n; ++i) {
    Point S;
    scanf("%d", &a[i]);
    if (a[i] == 3) {
      scanf("%d", &S.x);
      S.y = 1;
      ++m;
      res[m] = -1LL << 60;
      K[m] = S;
      a[i] = -m;
    } else {
      if (a[i] == 1) {
        scanf("%d%d", &S.x, &S.y);
        W[++p] = S;
        iid[i] = p;
        a[i] = p << 1;
      } else {
        int j;
        scanf("%d", &j);
        a[i] = iid[j - 1] << 1 | 1;
      }
    }
    A.push_back(a[i]);
  }
  divide(A);
  for (int i = 1; i <= m; ++i) {
    if (res[i] == -1LL << 60) {
      puts("EMPTY SET");
    } else {
      printf("%lld\n", res[i]);
    }
  }
}
int main() {
  work();
  return 0;
}