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 long long oo = 2E18;
const int None = 1E9 + 10;
struct point {
  long long x, y;
  point(long long _x = 0, long long _y = 0) { x = _x, y = _y; }
  point operator-(const point& w) const { return point(x - w.x, y - w.y); }
  point operator+(const point& w) const { return point(x + w.x, y + w.y); }
  point perp() const { return point(-y, x); }
  bool operator==(const point& w) const { return x == w.x && y == w.y; }
  void out() { cout << "(" << x << ',' << y << ")"; }
};
long long sgn(long long w) { return w == 0 ? 0 : (w > 0 ? 1 : -1); }
long long sp(const point& f, const point& s) { return f.x * s.x + f.y * s.y; }
long long vp(const point& f, const point& s) { return f.x * s.y - f.y * s.x; }
struct pointC : point {
  int kv;
  pointC(long long _x = 0, long long _y = 0) : point(_x, _y) {}
  void set_kv() {
    if (y > 0 || y == 0 && x >= 0)
      kv = 0;
    else
      kv = 1;
  }
  bool operator==(const pointC& w) const { return x == w.x && y == w.y; }
  bool operator<(const pointC& w) const {
    if (kv != w.kv) return kv < w.kv;
    return vp(*this, w) > 0;
  }
};
bool Compare(const point& f, const point& s) {
  return f.x != s.x ? f.x < s.x : f.y < s.y;
}
vector<point> Hull(vector<point> from) {
  if (from.empty()) return from;
  sort(from.begin(), from.end(), Compare);
  if (from[0] == from.back()) return vector<point>({from[0]});
  point a = from.front();
  point b = from.back();
  vector<point> lo = {a}, hi = {a};
  for (int i = 1; i < ((int)(from).size()); ++i) {
    if (i + 1 == ((int)(from).size()) || vp(b - a, from[i] - a) > 0) {
      while (((int)(hi).size()) > 1 &&
             vp(from[i] - hi[((int)(hi).size()) - 2],
                hi.back() - hi[((int)(hi).size()) - 2]) <= 0)
        hi.pop_back();
      hi.push_back(from[i]);
    }
    if (i + 1 == ((int)(from).size()) || vp(b - a, from[i] - a) < 0) {
      while (((int)(lo).size()) > 1 &&
             vp(from[i] - lo[((int)(lo).size()) - 2],
                lo.back() - lo[((int)(lo).size()) - 2]) >= 0)
        lo.pop_back();
      lo.push_back(from[i]);
    }
  }
  for (int i = ((int)(hi).size()) - 2; i > 0; --i) lo.push_back(hi[i]);
  return lo;
}
struct FindMax {
  vector<point> pts;
  vector<pair<pointC, int> > lines;
  void Build(const vector<point>& from) {
    pts = Hull(from);
    lines.clear();
    for (int i = 0; i < ((int)(pts).size()); ++i) {
      point a = pts[i], b;
      if (i + 1 < ((int)(pts).size()))
        b = pts[i + 1];
      else
        b = pts[0];
      b = b - a;
      lines.push_back(make_pair(pointC(b.x, b.y), i));
      lines.back().first.set_kv();
    }
    sort(lines.begin(), lines.end());
  }
  long long Query(long long x, long long y) {
    long long res = -oo;
    if (((int)(pts).size()) < 2) {
      for (auto& p : pts) (res) = max((res), (p.x * x + p.y * y));
    } else {
      pointC tar(-y, x);
      tar.set_kv();
      auto pos = lower_bound(lines.begin(), lines.end(), make_pair(tar, 0));
      if (pos == lines.end()) pos = lines.begin();
      int idx = pos->second;
      return x * pts[idx].x + y * pts[idx].y;
    }
    return res;
  }
};
const int BLOCK = 10000;
vector<int> op;
vector<long long> out;
vector<pair<int, pair<int, int> > > in;
struct Node {
  Node *l, *r;
  int lo, hi;
  vector<pair<int, int> > add;
  Node(int lo, int hi) {
    this->lo = lo, this->hi = hi;
    l = r = NULL;
  }
  static Node* Build(int lo, int hi) {
    Node* res = new Node(lo, hi);
    if (lo != hi) {
      int mid = (lo + hi) >> 1;
      res->l = Build(lo, mid);
      res->r = Build(mid + 1, hi);
    }
    return res;
  }
  void Add(int f, int t, int a, int b) {
    if (f <= lo && hi <= t)
      add.push_back(make_pair(a, b));
    else if (t < lo || hi < f)
      return;
    else
      l->Add(f, t, a, b), r->Add(f, t, a, b);
  }
};
void Solve(Node* vr, FindMax& fm, vector<point>& tmp) {
  if (vr->lo == vr->hi) {
    int idx = vr->lo;
    if (op[idx] != None) {
      long long res = fm.Query(op[idx], 1);
      for (const auto& p : tmp) (res) = max((res), (p.x * 1LL * op[idx] + p.y));
      for (const auto& p : vr->add)
        (res) = max((res), (p.first * 1LL * op[idx] + p.second));
      out[idx] = res;
    }
  } else {
    if (((int)(tmp).size()) + ((int)(vr->add).size()) <= BLOCK) {
      for (const auto& a : vr->add) tmp.push_back(point(a.first, a.second));
      Solve(vr->l, fm, tmp);
      Solve(vr->r, fm, tmp);
      for (int i = 0; i < ((int)(vr->add).size()); ++i) tmp.pop_back();
    } else {
      vector<point> tot = tmp;
      for (const auto& a : vr->add) tot.push_back(point(a.first, a.second));
      for (const auto& a : fm.pts) tot.push_back(a);
      FindMax fm1;
      fm1.Build(tot);
      vector<point> tmp1;
      Solve(vr->l, fm1, tmp1);
      Solve(vr->r, fm1, tmp1);
    }
  }
}
int main() {
  int n;
  scanf("%d", &n);
  op.resize(n), in.resize(n), out.resize(n);
  Node* root = Node::Build(0, n - 1);
  fill(op.begin(), op.end(), None);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &in[i].first);
    if (in[i].first == 1)
      scanf("%d%d", &in[i].second.first, &in[i].second.second);
    else
      scanf("%d", &in[i].second.first);
  }
  map<int, int> end;
  for (int i = n - 1; i >= 0; --i) {
    if (in[i].first == 2) end[in[i].second.first - 1] = i;
    if (in[i].first == 3) op[i] = in[i].second.first;
    if (in[i].first == 1) {
      int lo = i, hi = n - 1;
      if (end.count(i)) hi = end[i];
      root->Add(lo, hi, in[i].second.first, in[i].second.second);
    }
  }
  FindMax fm = FindMax();
  vector<point> tmp;
  Solve(root, fm, tmp);
  for (int i = 0; i < n; ++i)
    if (op[i] != None) {
      if (out[i] == -oo)
        printf("EMPTY SET\n");
      else
        printf("%I64d\n", out[i]);
    }
  return 0;
}