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 GCC optimize("Ofast")
using namespace std;
long long l[300005], r[300005], q[300005], ques[300005], mini = -2e18;
pair<long long, long long> p[300005];
vector<long long> vp;
vector<long long> v[1 << 20];
vector<double> vd[1 << 20];
bool cmp(long long x, long long y) { return p[x].first < p[y].first; }
double solve(long long x, long long y) {
  return 1.0 * (p[x].second - p[y].second) / (p[y].first - p[x].first);
}
void update(long long x, long long it) {
  while (!v[x].empty() && p[v[x].back()].first == p[it].first &&
         p[v[x].back()].second <= p[it].second) {
    v[x].pop_back();
    if (!v[x].empty()) vd[x].pop_back();
  }
  while (v[x].size() > 1 &&
         solve(v[x][v[x].size() - 2], it) > solve(v[x][v[x].size() - 1], it)) {
    v[x].pop_back();
    vd[x].pop_back();
  }
  v[x].emplace_back(it);
  if (v[x].size() > 1) vd[x].emplace_back(solve(v[x][v[x].size() - 2], it));
}
void update(long long x, long long l, long long r, long long tl, long long tr,
            long long it) {
  if (tl > r || l > tr) return;
  if (tl <= l && tr >= r) {
    update(x, it);
    return;
  }
  long long mid = (l + r) >> 1;
  update(x << 1, l, mid, tl, tr, it);
  update((x << 1) | 1, mid + 1, r, tl, tr, it);
}
long long get(long long x, long long it, long long pos) {
  if (v[x].empty()) {
    return mini;
  } else if (vd[x].empty()) {
    pair<long long, long long> t = p[v[x].back()];
    return t.first * it + t.second;
  } else {
    long long iter =
        lower_bound(vd[x].begin(), vd[x].end(), 1.0 * it) - vd[x].begin();
    pair<long long, long long> t = p[v[x][iter]];
    return t.first * it + t.second;
  }
}
long long query(long long x, long long l, long long r, long long it,
                long long pos) {
  long long re = get(x, it, pos);
  if (l == r) return re;
  long long mid = (l + r) >> 1;
  if (mid >= pos) {
    re = max(re, query(x << 1, l, mid, it, pos));
  } else
    re = max(re, query((x << 1) | 1, mid + 1, r, it, pos));
  return re;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; i++) {
    cin >> q[i];
    if (q[i] == 1) {
      cin >> p[i].first >> p[i].second;
      vp.emplace_back(i);
      l[i] = i;
      r[i] = n;
    } else if (q[i] == 2) {
      long long x;
      cin >> x;
      r[x] = i;
    } else {
      cin >> ques[i];
    }
  }
  sort(vp.begin(), vp.end(), cmp);
  for (auto u : vp) {
    update(1, 1, n, l[u], r[u], u);
  }
  for (long long i = 1; i <= n; i++)
    if (q[i] == 3) {
      long long t = query(1, 1, n, ques[i], i);
      if (t == mini) {
        cout << "EMPTY SET\n";
      } else
        cout << t << '\n';
    }
  return 0;
}