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 N = 1;
const long long big = 6e18;
long long block = 800;
const long long mod = 1e6;
long long n;
set<pair<long long, long long> > a;
vector<pair<long long, pair<long long, long long> > > t;
set<pair<long long, pair<long long, long long> > > cht;
vector<pair<long long, long long> > convex;
long double cross(pair<long long, long long> a, pair<long long, long long> b) {
  return (b.second - a.second + 0.0) / (a.first - b.first + 0.0);
}
void add(pair<long long, long long> a) {
  while (convex.size() > 1 &&
         cross(a, convex[convex.size() - 2]) >= cross(a, convex.back()))
    convex.pop_back();
  convex.push_back(a);
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  t.push_back({0, {0, 0}});
  for (int i = (0); i < (n); i += 1) {
    long long x, a, b = 0;
    cin >> x >> a;
    if (x == 1) cin >> b;
    t.push_back({x, {a, b}});
  }
  block = 3000;
  for (int i = 1; i <= n; i += block) {
    long long l = i, r = min(i + block, n + 1);
    set<pair<long long, pair<long long, long long> > > sub;
    for (int j = l; j < r; j++) {
      if (t[j].first == 2 && t[j].second.first < l) {
        pair<long long, pair<long long, long long> > del = {
            t[t[j].second.first].second.first,
            {t[t[j].second.first].second.second, t[j].second.first}};
        auto it = cht.find(del);
        cht.erase(it);
        sub.insert(del);
      }
    }
    for (auto u : cht) add({u.first, u.second.first});
    for (int j = l; j < r; j++) {
      if (t[j].first == 1) {
        cht.insert({t[j].second.first, {t[j].second.second, j}});
        sub.insert({t[j].second.first, {t[j].second.second, j}});
      }
      if (t[j].first == 2) {
        long long L = t[j].second.first;
        pair<long long, pair<long long, long long> > del = {
            t[L].second.first, {t[L].second.second, L}};
        auto it = sub.find(del);
        sub.erase(it);
        if (L >= l) {
          it = cht.find(del);
          cht.erase(it);
        }
      }
      if (t[j].first == 3) {
        long long ans = -big;
        if (sub.size() == 0 && cht.size() == 0) {
          cout << "EMPTY SET\n";
          continue;
        }
        long long x = t[j].second.first;
        for (auto u : sub) ans = max(ans, u.first * x + u.second.first);
        if (convex.size() > 0) {
          long long L = 1, R = convex.size() - 1;
          ans = max(convex[0].first * x + convex[0].second, ans);
          long double XX = x;
          while (L <= R) {
            long long m = (L + R) >> 1;
            ans = max(convex[m].first * x + convex[m].second, ans);
            if (cross(convex[m], convex[m - 1]) > XX)
              R = m - 1;
            else
              L = m + 1;
          }
        }
        cout << ans << '\n';
      }
    }
    convex.clear();
  }
}