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 BLOCK_SIZE = 1000;
const long long INF = 3e18;
struct TQuery {
  int Idx;
  int Type;
  union {
    struct {
      long long A;
      long long B;
    };
    struct {
      int Q;
    };
    struct {
      int EraseIdx;
    };
  };
};
struct TFrac {
  long long P;
  long long Q;
  TFrac() : P(0), Q(1) {}
  void Upd() {
    if (Q < 0) {
      P *= -1;
      Q *= -1;
    }
  }
  TFrac(long long p, long long q) : P(p), Q(q) { Upd(); }
  TFrac(long long p) : P(p), Q(1) {}
  TFrac operator+(const TFrac& f) const {
    return TFrac(P * f.Q + f.P * Q, Q * f.Q);
  }
  bool operator<(const TFrac& f) const { return P * f.Q < f.P * Q; }
  bool operator==(const TFrac& f) const { return P == f.P && Q == f.Q; }
};
struct TLine {
  long long A;
  long long B;
  int Idx;
};
bool operator<(const TLine& a, const TLine& b) {
  return a.A < b.A || (a.A == b.A && a.B < b.B);
}
TFrac Intersect(const TLine& a, const TLine& b) {
  long long A1 = a.A;
  long long B1 = a.B;
  long long A2 = b.A;
  long long B2 = b.B;
  return TFrac(B1 - B2, A2 - A1);
}
bool NeedErase(const TLine& a, const TLine& b, const TLine& c) {
  TFrac x1 = Intersect(a, b);
  TFrac x2 = Intersect(b, c);
  return x2 < x1 || (x2 == x1);
}
void MakeConvexHull(const vector<TLine>& all, int st, int to,
                    const vector<int>& erasedTime, vector<TLine>& convexHull,
                    vector<TLine>& buffer) {
  buffer.clear();
  buffer.reserve(all.size());
  for (int i = 0; i < (int)all.size(); ++i)
    if (all[i].Idx < st && erasedTime[all[i].Idx] >= to)
      buffer.push_back(all[i]);
  convexHull.clear();
  for (const TLine& l : buffer) {
    while (convexHull.size() >= 2 &&
           NeedErase(convexHull[convexHull.size() - 2],
                     convexHull[convexHull.size() - 1], l))
      convexHull.pop_back();
    convexHull.push_back(l);
  }
}
bool Check(const vector<TLine>& convexHull, int m, long long x) {
  TFrac p = Intersect(convexHull[m - 1], convexHull[m]);
  return p < TFrac(x) || p == TFrac(x);
}
long long FindInConvexHull(const vector<TLine>& convexHull, long long x) {
  if (convexHull.empty()) return -INF;
  int l = 0, r = (int)convexHull.size();
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (Check(convexHull, m, x)) {
      l = m;
    } else {
      r = m;
    }
  }
  return 1LL * convexHull[l].A * x + convexHull[l].B;
}
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<TQuery> q(n);
  for (int i = 0; i < n; ++i) {
    cin >> q[i].Type;
    q[i].Idx = i;
    switch (q[i].Type) {
      case 1:
        cin >> q[i].A >> q[i].B;
        break;
      case 2:
        cin >> q[i].EraseIdx;
        --q[i].EraseIdx;
        break;
      case 3:
        cin >> q[i].Q;
        break;
    }
  }
  vector<TLine> lines;
  lines.reserve(n);
  for (int i = 0; i < n; ++i)
    if (q[i].Type == 1) lines.push_back(TLine{q[i].A, q[i].B, q[i].Idx});
  sort(lines.begin(), lines.end());
  vector<int> erasedTime(n, n);
  for (int i = 0; i < n; ++i)
    if (q[i].Type == 2) erasedTime[q[i].EraseIdx] = i;
  vector<TLine> convexHull;
  vector<TLine> buffer;
  vector<long long> answer;
  answer.reserve(n);
  for (int st = 0; st < n; st += BLOCK_SIZE) {
    int to = min(n, st + BLOCK_SIZE);
    MakeConvexHull(lines, st, to, erasedTime, convexHull, buffer);
    for (int i = st; i < to; ++i) {
      if (q[i].Type == 3) {
        long long currentAnswer = -INF;
        for (int j = st; j < to; ++j) {
          if (q[j].Type == 1)
            if (j < i && erasedTime[j] > i)
              currentAnswer =
                  max(currentAnswer, 1LL * q[j].A * q[i].Q + q[j].B);
          if (q[j].Type == 2)
            if (q[j].EraseIdx < i && j > i)
              currentAnswer =
                  max(currentAnswer,
                      1LL * q[q[j].EraseIdx].A * q[i].Q + q[q[j].EraseIdx].B);
        }
        currentAnswer =
            max(currentAnswer, FindInConvexHull(convexHull, q[i].Q));
        answer.push_back(currentAnswer);
      }
    }
  }
  for (int i = 0; i < (int)answer.size(); ++i) {
    if (answer[i] == -INF) {
      cout << "EMPTY SET" << '\n';
    } else {
      cout << answer[i] << '\n';
    }
  }
  return 0;
}