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 inf = 1LL << 62;
const int Mod = 1e9 + 7;
int dcmp(double x) {
  if (fabs(x) <= 1e-5) return 0;
  return x < 0 ? -1 : 1;
}
struct Point {
  int x, y;
  int l, r;
  Point(long long x = 0, long long y = 0) : x(x), y(y) {}
  Point operator-(const Point &a) const { return Point(x - a.x, y - a.y); }
  Point operator+(const Point &a) const { return Point(x + a.x, y + a.y); }
  Point operator*(const double &a) const { return Point(x * a, y * a); }
  Point operator/(const double &a) const { return Point(x / a, y / a); }
  bool operator<(const Point &a) const {
    if (x == a.x) return y < a.y;
    return x < a.x;
  }
  bool operator==(const Point &a) const {
    return dcmp(x - a.x) == 0 && dcmp(y - a.y) == 0;
  }
  void read() { scanf("%d%d", &x, &y); }
  void out() { cout << "Bug: " << x << " " << y << endl; }
};
inline long long Cross(Point a, Point b) {
  return 1ll * a.x * b.y - 1ll * a.y * b.x;
}
inline double Dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
inline double dis(Point a) { return sqrt(Dot(a, a)); }
Point p[300100];
pair<int, int> q[300100];
int mp[300100], m, n;
vector<Point> T[300100 << 2];
long long ans[300100];
Point ch[300100];
int ty[300100];
void Insert(int L, int R, Point pp, int l, int r, int rt) {
  int mid = l + r >> 1;
  if (L <= l && r <= R) {
    T[rt].push_back(pp);
    return;
  }
  if (R <= mid)
    Insert(L, R, pp, l, mid, rt << 1);
  else if (L > mid)
    Insert(L, R, pp, mid + 1, r, rt << 1 | 1);
  else
    Insert(L, mid, pp, l, mid, rt << 1),
        Insert(mid + 1, R, pp, mid + 1, r, rt << 1 | 1);
}
void Query(int x, int now) {
  int l = 0, r = m - 1;
  while (l < r - 2) {
    int lmid = (l + l + r) / 3;
    int rmid = (l + r + r + 2) / 3;
    if (1ll * x * ch[lmid].x + ch[lmid].y < 1ll * x * ch[rmid].x + ch[rmid].y)
      l = lmid;
    else
      r = rmid;
  }
  for (int i = l; i <= r; i++)
    ans[now] = max(ans[now], 1ll * x * ch[i].x + ch[i].y);
}
void Down(int l, int r, int rt) {
  int mid = l + r >> 1;
  if (l < r) {
    Down(l, mid, rt << 1);
    Down(mid + 1, r, rt << 1 | 1);
  }
  m = 0;
  for (int i = 0; i < T[rt].size(); i++) {
    while (m > 1 && Cross(T[rt][i] - ch[m - 2], ch[m - 1] - ch[m - 2]) <= 0)
      m--;
    ch[m++] = T[rt][i];
  }
  for (int i = l; i <= r; i++) {
    if (ty[i] == 3) Query(mp[i], i);
  }
}
void solve() {
  cin >> n;
  memset(mp, 0, sizeof(mp));
  fill(ans, ans + 300100, -inf);
  for (int i = 0; i <= n * 4; i++) T[i].clear();
  memset(p, 0, sizeof(p));
  int ct = 0, pt = 0, now = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &ty[i]);
    if (ty[i] == 1) p[pt].read(), p[pt].l = i, p[pt].r = n, mp[i] = pt++, now++;
    if (ty[i] == 2) {
      scanf("%d", &m);
      p[mp[m]].r = i, now--;
    }
    if (ty[i] == 3) {
      scanf("%d", &mp[i]);
      if (now == 0) ty[i] = 4;
    }
  }
  sort(p, p + pt);
  for (int i = 0; i <= pt - 1; i++) Insert(p[i].l, p[i].r, p[i], 1, n, 1);
  Down(1, n, 1);
  for (int i = 1; i <= n; i++) {
    if (ty[i] == 4) puts("EMPTY SET");
    if (ty[i] == 3) cout << ans[i] << endl;
  }
}
int main() {
  int t = 1;
  while (t--) solve();
  return 0;
}