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 int N = 3e5 + 2;
const int M = 4e6 + 2;
const long long mod = 1e9 + 7;
const int inf = 2e9 + 3;
const long long INF = 3e18;
void data() {}
int n, dl[N], block = 5000, cnt;
set<pair<pair<long long, long long>, pair<long long, long long>>> al;
vector<pair<pair<long long, long long>, pair<long long, long long>>> bl[N], tmp,
    del;
pair<pair<long long, long long>, pair<long long, long long>> q[N];
vector<pair<long long, long long>> lines;
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> nw) {
  while ((int)lines.size() > 1) {
    int last = (int)lines.size() - 1;
    if (cross(lines[last], lines[last - 1]) < cross(lines[last - 1], nw)) break;
    lines.pop_back();
  }
  lines.push_back(nw);
}
long long mx(long long x) {
  if ((int)lines.size() == 0) return -INF;
  int l = 0;
  for (int i = (int)lines.size(); i >= 1; i /= 2) {
    while (l + i < (int)lines.size() &&
           cross(lines[l + i], lines[l + i - 1]) < x + 0.0) {
      l += i;
    }
  }
  long long ret = lines[0].first * x + lines[0].second;
  for (int i = 0; i <= 0; ++i) {
    if (0 <= l + i && l + i < (int)lines.size())
      ret = max(ret, lines[l + i].first * x + lines[l + i].second);
  }
  return ret;
}
int main() {
  data();
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    cnt += (i % block == 1);
    long long tp, a, b;
    scanf("%lld", &tp);
    if (tp == 1) {
      scanf("%lld %lld", &a, &b);
      bl[cnt].push_back(make_pair(make_pair(a, b), make_pair(i, tp)));
      q[i] = make_pair(make_pair(a, b), make_pair(i, tp));
    }
    if (tp == 2) {
      scanf("%lld", &a);
      bl[cnt].push_back(make_pair(make_pair(a, 0), make_pair(i, tp)));
      q[i] = make_pair(make_pair(a, 0), make_pair(i, tp));
    }
    if (tp == 3) {
      scanf("%lld", &a);
      bl[cnt].push_back(make_pair(make_pair(a, 0), make_pair(i, tp)));
      q[i] = make_pair(make_pair(a, 0), make_pair(i, tp));
    }
  }
  for (int i = 1; i <= cnt; ++i) {
    for (auto it : bl[i]) {
      if (it.second.second == 2) {
        dl[it.first.first] = 1;
        al.erase(q[it.first.first]);
        del.push_back(it);
      }
    }
    tmp.clear();
    lines.clear();
    for (auto it : al) add(it.first);
    for (auto it : bl[i]) {
      if (it.second.second == 1) {
        if (!dl[it.second.first]) tmp.push_back(it);
      }
      if (it.second.second == 3) {
        long long ans = -INF;
        for (auto iter : tmp) {
          if (!dl[iter.second.first]) {
            ans =
                max(ans, iter.first.first * it.first.first + iter.first.second);
          }
        }
        for (auto iter : del) {
          if (iter.first.first <= it.second.first &&
              it.second.first <= iter.second.first) {
            ans = max(ans, q[iter.first.first].first.first * it.first.first +
                               q[iter.first.first].first.second);
          }
        }
        ans = max(ans, mx(it.first.first));
        if (ans == -INF)
          printf("EMPTY SET\n");
        else
          printf("%lld\n", ans);
      }
    }
    lines.clear();
    del.clear();
    for (auto it : tmp) al.insert(it);
    for (auto it : al) add(it.first);
  }
}