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>
const long double EPS = 1e-10;
const long long int MOD = 1000000007ll;
const long long int mod1 = 1000000009ll;
const long long int mod2 = 1100000009ll;
int INF = 2147483645;
long long int INFINF = 9223372036854775807;
int debug = 0;
using namespace std;
void print(int a[], int s, int e) {
  for (int i = s; i <= e; i++) cout << a[i] << " ";
  cout << "\n";
}
void print(vector<int>& v, int s, int e) {
  for (int i = s; i <= e; i++) cout << v[i] << " ";
  cout << "\n";
}
void print(vector<int>& v) {
  for (int x : v) cout << x << " ";
  cout << "\n";
}
long long int bit_count(long long int _x) {
  long long int _ret = 0;
  while (_x) {
    if (_x % 2 == 1) _ret++;
    _x /= 2;
  }
  return _ret;
}
long long int bit(long long int _mask, long long int _i) {
  return (_mask & (1 << _i)) == 0 ? 0 : 1;
}
long long int powermod(long long int _a, long long int _b, long long int _m) {
  long long int _r = 1;
  while (_b) {
    if (_b % 2 == 1) _r = (_r * _a) % _m;
    _b /= 2;
    _a = (_a * _a) % _m;
  }
  return _r;
}
long long int add(long long int a, long long int b, long long int m = MOD) {
  long long int x = a + b;
  while (x >= m) x -= m;
  return x;
}
long long int sub(long long int a, long long int b, long long int m = MOD) {
  long long int x = a - b;
  while (x < 0) x += m;
  return x;
}
long long int mul(long long int a, long long int b, long long int m = MOD) {
  long long int x = a * b;
  x %= m;
  return x;
}
class CHT {
  bool isMax = true;

 public:
  CHT() {}
  struct line_segment {
    long long int a, b;
    double xLeft;
    enum Type { line, maxQuery, minQuery } type;
    long long int val;
    explicit line_segment(long long int aa = 0, long long int bb = 0)
        : a(aa), b(bb), xLeft(-INFINITY), type(Type::line), val(0) {}
    long long int valueAt(long long int x) const { return a * x + b; }
    friend bool dont_meet(const line_segment& l1, const line_segment& l2) {
      return l1.a == l2.a;
    }
    friend double meet(const line_segment& l1, const line_segment& l2) {
      return dont_meet(l1, l2) ? INFINITY : 1.0 * (l2.b - l1.b) / (l1.a - l2.a);
    }
    bool operator<(const line_segment& l2) const {
      if (l2.type == line) return this->a < l2.a;
      if (l2.type == maxQuery) return this->xLeft < l2.val;
      if (l2.type == minQuery) return this->xLeft > l2.val;
    }
  };
  std::set<line_segment> slopes;
  bool hasPrev(std::set<line_segment>::iterator it) {
    return it != slopes.begin();
  }
  bool hasNext(std::set<line_segment>::iterator it) {
    return it != slopes.end() && std::next(it) != slopes.end();
  }
  bool bad(const line_segment& l1, const line_segment& l2,
           const line_segment& l3) {
    return meet(l1, l3) <= meet(l1, l2);
  }
  bool bad(std::set<line_segment>::iterator it) {
    return hasPrev(it) && hasNext(it) &&
           (isMax && bad(*std::prev(it), *it, *std::next(it)) ||
            !isMax && bad(*std::next(it), *it, *std::prev(it)));
  }
  std::set<line_segment>::iterator fix(std::set<line_segment>::iterator it) {
    if (isMax && !hasPrev(it) || !isMax && !hasNext(it)) return it;
    double val = meet(*it, isMax ? *std::prev(it) : *std::next(it));
    line_segment buf(*it);
    it = slopes.erase(it);
    buf.xLeft = val;
    it = slopes.insert(it, buf);
    return it;
  }
  void insert_Line(long long int a, long long int b) {
    line_segment l3 = line_segment(a, b);
    auto it = slopes.lower_bound(l3);
    if (it != slopes.end() && dont_meet(*it, l3)) {
      if (isMax && it->b < b || !isMax && it->b > b)
        it = slopes.erase(it);
      else
        return;
    }
    it = slopes.insert(it, l3);
    if (bad(it)) {
      slopes.erase(it);
      return;
    }
    while (hasPrev(it) && bad(std::prev(it))) slopes.erase(std::prev(it));
    while (hasNext(it) && bad(std::next(it))) slopes.erase(std::next(it));
    it = fix(it);
    if (hasPrev(it)) fix(prev(it));
    if (hasNext(it)) fix(next(it));
  }
  long long int evaluate(long long int x) const {
    if (slopes.empty()) {
      if (isMax)
        return (long long int)-INFINF;
      else
        return (long long int)INFINF;
    }
    line_segment q;
    q.val = x;
    q.type =
        isMax ? line_segment::Type::maxQuery : line_segment::Type::minQuery;
    auto bestLine = slopes.lower_bound(q);
    if (isMax) --bestLine;
    return bestLine->valueAt(x);
  }
};
int N;
int Type[300010];
int A[300010], B[300010];
CHT segtree[1200010];
bool removed[300010];
long long int ans;
void update(int s, int e, int x, int y, int idx, int i) {
  if (s == x && e == y) {
    segtree[idx].insert_Line(A[i], B[i]);
    return;
  }
  int mid = (s + e) >> 1;
  if (y <= mid)
    update(s, mid, x, y, 2 * idx + 1, i);
  else if (x > mid)
    update(mid + 1, e, x, y, 2 * idx + 2, i);
  else {
    update(s, mid, x, mid, 2 * idx + 1, i);
    update(mid + 1, e, mid + 1, y, 2 * idx + 2, i);
  }
}
void query(int s, int e, int x, int idx, int i) {
  ans = max(ans, segtree[idx].evaluate(A[i]));
  if (s == e) return;
  int mid = (s + e) >> 1;
  if (x <= mid)
    query(s, mid, x, 2 * idx + 1, i);
  else
    query(mid + 1, e, x, 2 * idx + 2, i);
}
int main() {
  srand(time(NULL));
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &Type[i]);
    if (Type[i] == 1) {
      scanf("%d", &A[i]);
      scanf("%d", &B[i]);
    } else if (Type[i] == 2) {
      int prev;
      scanf("%d", &prev);
      update(1, N, prev, i, 0, prev);
      removed[prev] = true;
    } else {
      scanf("%d", &A[i]);
    }
  }
  for (int i = 1; i <= N; i++) {
    if (Type[i] == 1 && (!removed[i])) {
      update(1, N, i, N, 0, i);
    }
  }
  for (int i = 1; i <= N; i++) {
    if (Type[i] == 3) {
      ans = -INFINF;
      query(1, N, i, 0, i);
      if (ans == -INFINF)
        printf("EMPTY SET\n");
      else
        printf("%lld\n", ans);
    }
  }
  return 0;
}