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>
#pragma warning(disable : 4996)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("-ffloat-store")
using namespace std;
clock_t time_p = clock();
void aryanc403() {
  time_p = clock() - time_p;
  cerr << "Time Taken : " << (float)(time_p) / CLOCKS_PER_SEC << "\n";
}
const long long int INF = 0xFFFFFFFFFFFFFFFL;
long long int seed;
mt19937 rng(seed = chrono::steady_clock::now().time_since_epoch().count());
inline long long int rnd(long long int l = 0, long long int r = INF) {
  return uniform_int_distribution<long long int>(l, r)(rng);
}
class CMP {
 public:
  bool operator()(pair<long long int, long long int> a,
                  pair<long long int, long long int> b) {
    return !(a.first < b.first || a.first == b.first && a.second <= b.second);
  }
};
void add(map<long long int, long long int> &m, long long int x,
         long long int cnt = 1) {
  auto jt = m.find(x);
  if (jt == m.end())
    m.insert({x, cnt});
  else
    jt->second += cnt;
}
void del(map<long long int, long long int> &m, long long int x,
         long long int cnt = 1) {
  auto jt = m.find(x);
  if (jt->second <= cnt)
    m.erase(jt);
  else
    jt->second -= cnt;
}
bool cmp(const pair<long long int, long long int> &a,
         const pair<long long int, long long int> &b) {
  return a.first < b.first || (a.first == b.first && a.second < b.second);
}
struct cht {
  struct Line {
    long long int a;
    long long int b;
    long long int val;
    double xLeft;
    bool type;
    Line(long long int _a = 0, long long int _b = 0) {
      a = _a;
      b = _b;
      xLeft = -INF;
      type = 0;
      val = 0;
    }
    long long int valueAt(long long int x) const { return 1LL * a * x + b; }
    friend bool areParallel(const Line &l1, const Line &l2) {
      return l1.a == l2.a;
    }
    friend double intersectX(const Line &l1, const Line &l2) {
      return areParallel(l1, l2) ? INF : (l2.b - l1.b) / (double)(l1.a - l2.a);
    }
    bool operator<(const Line &l2) const {
      if (!l2.type) return a < l2.a;
      return xLeft > l2.val;
    }
  };
  set<Line> hull;
  void init() { hull.clear(); }
  bool hasPrev(set<Line>::iterator it) { return it != hull.begin(); }
  bool hasNext(set<Line>::iterator it) {
    return it != hull.end() && next(it) != hull.end();
  }
  bool irrelevant(const Line &l1, const Line &l2, const Line &l3) {
    return intersectX(l1, l3) <= intersectX(l1, l2);
  }
  bool irrelevant(set<Line>::iterator it) {
    return hasPrev(it) && hasNext(it) &&
           (irrelevant(*next(it), *it, *prev(it)));
  }
  set<Line>::iterator updateLeftBorder(set<Line>::iterator it) {
    if (!hasNext(it)) {
      return it;
    }
    double val = intersectX(*it, *next(it));
    Line buf(*it);
    it = hull.erase(it);
    buf.xLeft = val;
    it = hull.insert(it, buf);
    return it;
  }
  void addLine(long long int a, long long int b) {
    Line l3 = Line(a, b);
    auto it = hull.lower_bound(l3);
    if (it != hull.end() && areParallel(*it, l3)) {
      if (it->b > b) {
        it = hull.erase(it);
      } else {
        return;
      }
    }
    it = hull.insert(it, l3);
    if (irrelevant(it)) {
      hull.erase(it);
      return;
    }
    while (hasPrev(it) && irrelevant(prev(it))) {
      hull.erase(prev(it));
    }
    while (hasNext(it) && irrelevant(next(it))) {
      hull.erase(next(it));
    }
    it = updateLeftBorder(it);
    if (hasPrev(it)) {
      updateLeftBorder(prev(it));
    }
    if (hasNext(it)) {
      updateLeftBorder(next(it));
    }
  }
  long long int getBest(long long int x) {
    if (hull.empty()) return INF;
    Line q;
    q.val = x;
    q.type = 1;
    auto bestLine = hull.lower_bound(q);
    if (bestLine == hull.end()) {
      return INF;
    }
    return bestLine->valueAt(x);
  }
};
const long long int mod = 1000000007L;
const long long int maxN = 300000L;
long long int T, n, i, j, k, in, cnt, l, r, u, v, x, y;
long long int m;
string s;
cht f[4 * maxN + 5];
pair<long long int, long long int> aa[maxN + 5];
long long int tout[maxN + 5];
vector<pair<long long int, long long int> > qur;
void add(long long int id, long long int l, long long int r, long long int L,
         long long int R, pair<long long int, long long int> x) {
  if (L > R || l > r || r < L || R < l) return;
  if (L <= l && r <= R) {
    f[id].addLine(x.first, x.second);
    return;
  }
  long long int m = (l + r) / 2;
  add(2 * id, l, m, L, R, x);
  add(2 * id + 1, m + 1, r, L, R, x);
}
long long int query(long long int id, long long int l, long long int r,
                    long long int i, long long int x) {
  if (r < i || i < l) return -INF;
  long long int ans = -INF;
  long long int m = (l + r) / 2;
  ans = max(ans, -f[id].getBest(x));
  if (l == r) return ans;
  ans = max(ans, query(2 * id, l, m, i, x));
  ans = max(ans, query(2 * id + 1, m + 1, r, i, x));
  return ans;
}
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  {
    cin >> n;
    for (i = (1); i <= (n); ++i) {
      cin >> T;
      if (T == 1) {
        cin >> x >> y;
        x *= -1;
        y *= -1;
        tout[i] = n + 1;
        aa[i] = {x, y};
      } else if (T == 2) {
        cin >> x;
        tout[x] = i;
      } else {
        cin >> x;
        qur.push_back({i, x});
      }
    }
    for (i = (1); i <= (n); ++i) add(1, 1, n, i, tout[i], aa[i]);
    for (auto x : qur) {
      long long int ans = query(1, 1, n, x.first, x.second);
      if (ans == -INF)
        cout << "EMPTY SET"
             << "\n";
      else
        cout << ans << "\n";
    }
  }
  aryanc403();
  return 0;
}