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 INF = 5 * 1e18;
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << p.first << " " << p.second;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (size_t i = 0; i < v.size(); ++i) {
    if (i) os << " ";
    os << v[i];
  }
  return os;
}
template <class ItemX>
struct SQRTDecomposition {
  struct Item : ItemX {
    Item(const ItemX& item, int BlockId, int Order, int OrderInBlock)
        : ItemX(item),
          BlockId(BlockId),
          Order(Order),
          OrderInBlock(OrderInBlock) {}
    int BlockId, Order, OrderInBlock;
  };
  SQRTDecomposition(const vector<ItemX>& q, int blockSize = -1) {
    BLOCK_SIZE = blockSize == -1 ? sqrt(q.size()) + 1 : blockSize;
    for (int i = (0); i < (q.size()); ++i) {
      if (i % BLOCK_SIZE == 0) items.push_back(vector<Item>());
      items.back().push_back(Item(q[i], i / BLOCK_SIZE, i, i % BLOCK_SIZE));
    }
  }
  ItemX& operator[](int index) {
    return items[index / BLOCK_SIZE][index % BLOCK_SIZE];
  }
  int size() const { return SIZE; }
  int BLOCK_SIZE, SIZE;
  vector<vector<Item>> items;
};
double totalTime = 0;
template <class FUNC, class RET = int>
RET timeIt(const FUNC& fn) {
  clock_t start = clock();
  RET res = fn();
  totalTime += clock() - start;
  return res;
}
struct Line {
  long long m, b;
  mutable function<const Line*()> succ;
  bool operator<(const Line& rhs) const {
    if (rhs.b != -(1LL << 62)) return m < rhs.m;
    const Line* s = succ();
    if (!s) return 0;
    long long x = rhs.m;
    return b - s->b < (s->m - m) * x;
  }
};
struct HullDynamic : public multiset<Line> {
  bool bad(iterator y) {
    auto z = next(y);
    if (y == begin()) {
      if (z == end()) return false;
      return y->m == z->m && y->b <= z->b;
    }
    auto x = prev(y);
    if (z == end()) return y->m == x->m && y->b <= x->b;
    return (x->b - y->b) * (z->m - y->m) >= (y->b - z->b) * (y->m - x->m);
  }
  void insert_line(long long m, long long b) {
    auto y = insert({m, b});
    y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
    if (bad(y)) {
      erase(y);
      return;
    }
    while (next(y) != end() && bad(next(y))) erase(next(y));
    while (y != begin() && bad(prev(y))) erase(prev(y));
  }
  long long eval(long long x) {
    auto l = *lower_bound({x, -(1LL << 62)});
    return l.m * x + l.b;
  }
};
struct ConvexHullTrick : vector<pair<long long, long long>> {
  ConvexHullTrick(const vector<pair<long long, long long>>& v)
      : vector<pair<long long, long long>>(v) {
    pointer = 0;
    build();
  }
  bool bad(int l1, int l2, int l3) {
    return (at(l3).second - at(l1).second) * (at(l1).first - at(l2).first) <
           (at(l2).second - at(l1).second) * (at(l1).first - at(l3).first);
  }
  void build() {
    vector<pair<long long, long long>> lines(*this);
    sort(lines.begin(), lines.end());
    clear();
    for (const auto& line : lines) {
      push_back(line);
      while (size() >= 3 && bad(size() - 3, size() - 2, size() - 1))
        erase(end() - 2);
    }
  }
  long long f(int l, long long x) { return at(l).first * x + at(l).second; }
  long long eval(long long x) {
    pointer = 0;
    if (pointer >= (int)size()) pointer = size() - 1;
    int lo = 0, hi = size() - 1;
    while (lo != hi) {
      int mi = (lo + hi) / 2;
      if (at(mi).second - at(mi + 1).second <
          (at(mi + 1).first - at(mi).first) * x)
        lo = mi + 1;
      else
        hi = mi;
    }
    return f(lo, x);
    while (pointer < (int)size() - 1 &&
           at(pointer + 1).first * x + at(pointer + 1).second <
               at(pointer).first * x + at(pointer).second)
      pointer++;
    return at(pointer).first * x + at(pointer).second;
  }
  int pointer;
};
struct query {
  int type;
  long long m, b;
};
int main() {
  ios::sync_with_stdio(0);
  int n;
  scanf("%d", &n);
  vector<query> queries(n);
  map<int, pair<long long, long long>> lines;
  for (int i = (0); i < (n); ++i) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int a, b;
      scanf("%d%d", &a, &b);
      queries[i] = {1, a, b};
    } else if (t == 2) {
      int x;
      scanf("%d", &x);
      queries[i] = {2, x - 1, x - 1};
    } else {
      int q;
      scanf("%d", &q);
      queries[i] = {3, q, q};
    }
  }
  SQRTDecomposition<query> qrs(queries, 5000);
  int cnt = 0;
  for (const auto& block : qrs.items) {
    map<int, pair<long long, long long>> tmp_lines;
    for (const auto& query : block) {
      if (query.type == 2) {
        if (lines.count(query.m)) tmp_lines[query.m] = lines[query.m];
        lines.erase(query.m);
      }
    }
    HullDynamic hull;
    for (const auto& line : lines)
      hull.insert_line(line.second.first, line.second.second);
    for (const auto& query : block) {
      if (query.type == 1) {
        ++cnt;
        lines.insert({query.Order, {query.m, query.b}});
        tmp_lines.insert({query.Order, {query.m, query.b}});
      } else if (query.type == 2) {
        --cnt;
        lines.erase(query.m);
        tmp_lines.erase(query.m);
      } else if (query.type == 3) {
        if (!cnt) {
          puts("EMPTY SET");
        } else {
          long long res = -5 * 1e18;
          if (!hull.empty()) res = hull.eval(query.m);
          for (const auto& line : tmp_lines)
            res = max(res, line.second.first * query.m + line.second.second);
          printf("%lld\n", res);
        }
      }
    }
  }
  return 0;
}