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 = 2e18;
const long long maxn = 3e5 + 7;
long long kq[maxn];
struct Segment {
  long long a, b;
  bool operator<(const Segment &other) const {
    if (this->a == other.a) return this->b < other.b;
    return this->a < other.a;
  }
  long long Val(long long x) { return a * x + b; }
};
bool Bad(Segment i, Segment j, Segment k) {
  return (i.b - k.b) * (i.a - j.a) >= (j.b - i.b) * (k.a - i.a);
}
struct Hull {
  vector<Segment> vt;
  long long cur = 0;
  void Add(Segment x) {
    while (true) {
      if (vt.size() > 0 && vt.back().a == x.a) {
        vt.pop_back();
        continue;
      }
      if (vt.size() > 1 && Bad(vt[vt.size() - 2], vt[vt.size() - 1], x)) {
        vt.pop_back();
        continue;
      }
      vt.push_back(x);
      return;
    }
  }
  long long Query(long long x) {
    if (vt.size() == 0) return -Inf;
    cur = min(cur, (long long)vt.size() - 1);
    while (cur + 1 < vt.size() && vt[cur].Val(x) < vt[cur + 1].Val(x)) {
      cur++;
    }
    return vt[cur].Val(x);
  }
} IT[4 * maxn];
void Update(long long id, long long l, long long r, long long u, long long v,
            Segment x) {
  if (l > v || r < u) return;
  if (u <= l && r <= v) {
    IT[id].Add(x);
    return;
  }
  long long mid = l + r >> 1;
  Update(id * 2, l, mid, u, v, x);
  Update(id * 2 + 1, mid + 1, r, u, v, x);
}
long long n, End[maxn];
vector<pair<Segment, long long>> vt;
vector<pair<long long, long long>> ans;
vector<long long> gau;
long long Query(long long id, long long l, long long r, long long pos,
                long long val) {
  long long gau = IT[id].Query(val);
  if (l < r) {
    long long mid = l + r >> 1;
    if (pos <= mid)
      gau = max(gau, Query(id * 2, l, mid, pos, val));
    else
      gau = max(gau, Query(id * 2 + 1, mid + 1, r, pos, val));
  }
  return gau;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; i++) End[i] = n;
  for (long long i = 1; i <= n; i++) {
    long long type;
    cin >> type;
    if (type == 1) {
      long long a, b;
      cin >> a >> b;
      vt.push_back({{a, b}, i});
    } else if (type == 2) {
      long long x;
      cin >> x;
      End[x] = i;
    } else {
      long long x;
      cin >> x;
      ans.push_back({x, i});
      gau.push_back(i);
    }
  }
  sort(vt.begin(), vt.end());
  sort(ans.begin(), ans.end());
  for (auto i : vt) {
    Update(1, 1, n, i.second, End[i.second], i.first);
  }
  for (auto i : ans) {
    kq[i.second] = Query(1, 1, n, i.second, i.first);
  }
  for (auto i : gau) {
    if (kq[i] == -Inf)
      cout << "EMPTY SET"
           << "\n";
    else
      cout << kq[i] << '\n';
  }
}