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;
mt19937 bruh(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e6 + 2;
const int M = 1e5;
const int mod = 0;
const int inf = 1e9;
const long long INF = 3e18 + 1;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
void files() {
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
}
struct node {
  node *l, *r;
  pair<long long, long long> val;
  node(pair<long long, long long> val = {0, -INF}) : val(val) {
    l = nullptr;
    r = nullptr;
  }
} *r = new node();
struct li_chao {
  stack<pair<node *, pair<long long, long long>>> s;
  void save() { s.push({nullptr, {-INF, -INF}}); }
  void rollback() {
    while (s.top().first != nullptr) {
      s.top().first->val = s.top().second;
      s.pop();
    }
    s.pop();
  }
  node *upd(pair<long long, long long> val, node *v = r, long long tl = -inf,
            long long tr = inf) {
    if (v == nullptr) v = new node();
    if (tl == tr) return v;
    long long tm = tl + tr >> 1;
    if (v->val.first * tm + v->val.second <= val.first * tm + val.second) {
      s.push({v, v->val});
      swap(val, v->val);
    }
    if (v->val.first * tl + v->val.second <= val.first * tl + val.second)
      v->l = upd(val, v->l, tl, tm);
    else
      v->r = upd(val, v->r, tm + 1, tr);
    return v;
  }
  long long get(long long x, node *v = r, long long tl = -inf,
                long long tr = inf) {
    if (v == nullptr) return -INF;
    long long tm = tl + tr >> 1;
    if (tl == tr) return v->val.first * x + v->val.second;
    if (x <= tm)
      return max(v->val.first * x + v->val.second, get(x, v->l, tl, tm));
    else
      return max(v->val.first * x + v->val.second, get(x, v->r, tm + 1, tr));
  }
} LI;
int n, del[N];
pair<long long, long long> was[N];
long long ans[N];
struct tree {
  vector<pair<long long, long long>> t[N];
  pair<long long, long long> q[N];
  set<pair<long long, long long>> vals;
  void upd(int l, int r, pair<long long, long long> val, int v = 1, int tl = 1,
           int tr = n) {
    if (l <= tl && tr <= r) {
      t[v].push_back(val);
      return;
    }
    if (r < tl || tr < l) return;
    int tm = tl + tr >> 1;
    upd(l, r, val, v * 2, tl, tm);
    upd(l, r, val, v * 2 + 1, tm + 1, tr);
  }
  void dfs(int v = 1, int tl = 1, int tr = n) {
    LI.save();
    for (auto it : t[v]) {
      r = LI.upd(it);
    }
    if (tl == tr) {
      ans[tl] = LI.get(q[tl].first);
      LI.rollback();
      return;
    }
    int tm = tl + tr >> 1;
    dfs(v * 2, tl, tm);
    dfs(v * 2 + 1, tm + 1, tr);
    LI.rollback();
  }
} t;
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    ans[i] = -INF;
    long long tp, a, b;
    cin >> tp >> a;
    if (tp == 1) {
      cin >> b;
      was[i] = {a, b};
      del[i] = -1;
    }
    if (tp == 2) {
      t.upd(a, i - 1, was[a]);
      del[a] = 1;
    }
    if (tp == 3) {
      t.q[i] = {a, 1};
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (del[i] == -1) {
      t.upd(i, n, was[i]);
    }
  }
  t.dfs();
  for (int i = 1; i <= n; ++i) {
    if (t.q[i].second == 1) {
      if (ans[i] == -INF)
        cout << "EMPTY SET\n";
      else
        cout << ans[i] << '\n';
    }
  }
}