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>
int sgn(int a) {
  if (!a) return 0;
  if (a > 0) return 1;
  return -1;
}
int di(int a, int b) {
  if (!a) return 0;
  if (sgn(a) == sgn(b)) return a / b;
  return a / b - 1;
}
struct query {
  int t, a, b;
};
const int N = 300000;
const int K = 15000;
int n;
long long ans[N];
query q[N];
bool rm[N];
int main() {
  scanf("%d", &n);
  memset(ans, 0xc0, 8 * n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &q[i].t);
    if (q[i].t == 1)
      scanf("%d%d", &q[i].a, &q[i].b);
    else
      scanf("%d", &q[i].a);
    if (q[i].t == 2) --q[i].a;
  }
  std::deque<std::pair<int, int> > d;
  std::vector<std::pair<int, int> > pt;
  std::vector<int> cur;
  std::set<std::pair<int, int> > l;
  for (int i = 0; i < n; i += K) {
    if (i)
      for (int j = i - K; j < i; ++j)
        if (q[j].t == 1 && !rm[j]) l.insert(std::make_pair(q[j].a, q[j].b));
    for (int j = i; j < std::min(i + K, n); ++j) {
      if (q[j].t == 3)
        pt.push_back(std::make_pair(q[j].a, j));
      else if (q[j].t == 2 && q[j].a < i) {
        cur.push_back(q[j].a);
        l.erase(std::make_pair(q[q[j].a].a, q[q[j].a].b));
      }
    }
    std::sort(pt.begin(), pt.end());
    for (std::set<std::pair<int, int> >::iterator it = l.begin(); it != l.end();
         ++it)
      if (d.empty() || d.back().first != it->first ||
          it->second > d.back().second && (d.pop_back(), true)) {
        while (d.size() > 1 &&
               di(d.back().second - it->second, it->first - d.back().first) <=
                   di(d.back().second - d[(int)d.size() - 2].second,
                      d[(int)d.size() - 2].first - d.back().first))
          d.pop_back();
        d.push_back(*it);
      }
    if (!l.empty())
      for (int i = 0; i < (int)pt.size(); ++i) {
        while (d.size() > 1 &&
               (long long)d[0].first * pt[i].first + d[0].second <=
                   (long long)d[1].first * pt[i].first + d[1].second)
          d.pop_front();
        ans[pt[i].second] = (long long)d[0].first * pt[i].first + d[0].second;
      }
    for (int j = i; j < std::min(i + K, n); ++j) {
      if (q[j].t == 3) {
        bool any = !l.empty();
        for (int k = 0; k < (int)cur.size(); ++k)
          if (!rm[cur[k]]) {
            any = true;
            ans[j] =
                std::max(ans[j], (long long)q[j].a * q[cur[k]].a + q[cur[k]].b);
          }
        if (any)
          printf("%lld\n", ans[j]);
        else
          printf("EMPTY SET\n");
      } else if (q[j].t == 2)
        rm[q[j].a] = true;
      else
        cur.push_back(j);
    }
    d.clear();
    pt.clear();
    cur.clear();
  }
  return 0;
}