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 P {
  long long x, y;
  void read() { scanf("%lld%lld", &x, &y); }
  void write() const { printf("(%lld,%lld)", x, y); }
  long long operator*(const P& b) const { return x * b.y - y * b.x; }
  P operator+(const P& b) const { return P{x + b.x, y + b.y}; }
  P operator-(const P& b) const { return P{x - b.x, y - b.y}; }
  bool operator<(const P& b) const {
    return make_pair(x, y) < make_pair(b.x, b.y);
  }
  bool operator==(const P& b) const {
    return make_pair(x, y) == make_pair(b.x, b.y);
  }
  bool underLine(const P& a, const P& b) const {
    return (b - a) * (*this - a) <= 0;
  }
};
long long Z;
int tak_dupsko;
struct Node {
  int a_size, b_size;
  P *a, *b, *first;
  Node *L, *R;
  int size() { return a_size + b_size; }
  void check() {
    assert((L == NULL) == (R == NULL));
    if (L != NULL) {
      assert((a == NULL) == L->empty());
      assert((b == NULL) == R->empty());
    }
    if (L == NULL) {
      assert(size() == 0 || size() == 1);
    } else
      assert(size() <= L->size() + R->size());
  }
  bool empty() { return size() == 0; }
  bool isLeaf() { return L == NULL; }
  bool nonLeaf() { return !isLeaf(); }
  void act() {
    if (isLeaf()) {
      check();
      return;
    }
    if (L->size())
      first = L->first;
    else if (R->size())
      first = R->first;
    else
      first = NULL;
    if (L->empty() || R->empty()) {
      a = L->first;
      a_size = L->size();
      b = R->first;
      b_size = R->size();
      check();
      return;
    }
    assert(L->size() && R->size());
    a_size = b_size = 1;
    act(L, R);
    check();
  }

 private:
  void act(Node* inter1, Node* inter2) {
    ++Z;
    if (inter1->size() == 1 && inter2->size() == 1) {
      a = inter1->first;
      b = inter2->first;
      return;
    }
    P *A = inter1->a, *B = inter1->b;
    P *C = inter2->a, *D = inter2->b;
    if (inter1->size() > 1) {
      if (A == NULL) return act(inter1->R, inter2);
      if (B == NULL) return act(inter1->L, inter2);
    }
    if (inter2->size() > 1) {
      if (C == NULL) return act(inter1, inter2->R);
      if (D == NULL) return act(inter1, inter2->L);
    }
    auto remA = [&] {
      a_size += inter1->a_size;
      a_size -= inter1->R->size() - inter1->b_size;
      act(inter1->R, inter2);
    };
    auto remB = [&] { return act(inter1->L, inter2); };
    auto remC = [&] { return act(inter1, inter2->R); };
    auto remD = [&] {
      b_size += inter2->b_size;
      b_size -= inter2->L->size() - inter2->a_size;
      act(inter1, inter2->L);
    };
    if (inter1->size() == 1) {
      if (C->underLine(*inter1->first, *D))
        return remC();
      else
        return remD();
    }
    if (inter2->size() == 1) {
      if (B->underLine(*A, *inter2->first))
        return remB();
      else
        return remA();
    }
    if (B->underLine(*A, *C) || B->underLine(*A, *D) ||
        B->underLine(*A, *inter2->first))
      return remB();
    if (C->underLine(*B, *D)) return remC();
    int a_memo = a_size, b_memo = b_size;
    remA();
    if (B->underLine(*A, *b)) {
      a_size = a_memo;
      b_size = b_memo;
      assert(tak_dupsko < 300 * 1000);
      do {
        inter1 = inter1->L;
      } while (inter1->nonLeaf() &&
               (inter1->b == NULL ||
                (inter1->a != NULL && inter1->b->underLine(*inter1->a, *b))));
      remD();
    }
  }

 public:
  long long query(long long mul) {
    auto evaluate = [&](P p) { return mul * p.x + p.y; };
    if (size() == 1) return evaluate(*first);
    if (L->empty()) return R->query(mul);
    if (R->empty()) return L->query(mul);
    if (evaluate(*a) > evaluate(*b))
      return L->query(mul);
    else
      return R->query(mul);
  }
};
const int UPPER = 0, LOWER = 1;
const int REPS = 1;
long long done[1 << 21];
struct Hull {
  vector<Node> tr[2];
  vector<P> all;
  int pot;
  int getID(const P& a, int type) const {
    int tmp = lower_bound(all.begin(), all.end(), a) - all.begin();
    assert(all[tmp] == a);
    return tmp;
  }
  Hull(vector<P> w) {
    sort(w.begin(), w.end());
    w.resize(unique(w.begin(), w.end()) - w.begin());
    all = w;
    pot = 1;
    while (pot < (int)all.size()) pot *= 2;
    for (int rep = 0; rep < REPS; ++rep) {
      vector<Node>& t = tr[rep];
      t.clear();
      t.resize(2 * pot);
      for (int i = 1; i < pot; ++i) {
        t[i].L = &t[2 * i];
        t[i].R = &t[2 * i + 1];
      }
    }
    for (int i = 0; i < (int)all.size(); ++i) todo.push(pot + i);
  }
  priority_queue<int> todo;
  void change(const P& last) {
    for (int type = 0; type < REPS; ++type) {
      int id = getID(last, type);
      P* which_point = &all[id];
      if (type == LOWER) id = (int)all.size() - 1 - id;
      Node& tmp = tr[type][pot + id];
      if (tmp.empty()) {
        tmp.a_size = 1;
        tmp.first = which_point;
      } else {
        tmp.a_size = 0;
        tmp.first = NULL;
      }
      todo.push(pot + id);
    }
  }
  void query(long long mul) {
    static long long T = 0;
    ++T;
    while (!todo.empty()) {
      int id = todo.top();
      todo.pop();
      if (done[id] == T) continue;
      done[id] = T;
      tr[0][id].act();
      if (id != 1) todo.push(id / 2);
    }
    todo = priority_queue<int>();
    if (tr[UPPER][1].size() == 0) {
      puts("EMPTY SET");
      return;
    } else
      printf("%lld\n", tr[0][1].query(mul));
  }
};
const int nax = 6e5 + 5;
int type[nax], val[nax];
P p[nax];
int main() {
  int n;
  scanf("%d", &n);
  vector<P> w;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &type[i]);
    if (type[i] == 1) {
      p[i].read();
      w.push_back(p[i]);
    } else
      scanf("%d", &val[i]);
  }
  Hull hull(w);
  map<P, int> m;
  for (int i = 1; i <= n; ++i) {
    if (type[i] == 1) {
      if (m[p[i]]++ == 0) hull.change(p[i]);
    } else if (type[i] == 2) {
      if (--m[p[val[i]]] == 0) hull.change(p[val[i]]);
    } else {
      assert(type[i] == 3);
      hull.query(val[i]);
    }
  }
  cerr << "dupsko = " << tak_dupsko << "\n";
  cerr << "Z = " << Z << "\n";
}