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 MAXN = 4e5 + 10;
const long long INF = 2e18;
const long double EPS = 1e-9;
struct Line {
  int a, b;
  long double inter(const Line& l) const {
    assert(a != l.a);
    return (long double)(l.b - b) / (a - l.a);
  }
  Line() {}
  Line(int a, int b) : a(a), b(b) {}
  long long get(int x) { return a * 1ll * x + b; }
};
struct Hull {
  vector<Line> st;
  void push(const Line& l) {
    while (((int)(st).size()) >= 2) {
      const Line& l1 = st[((int)(st).size()) - 2];
      const Line& l2 = st[((int)(st).size()) - 1];
      if (l2.a == l.a) {
        if (l.b > l2.b) {
          st.pop_back();
          continue;
        } else {
          return;
        }
      }
      long double x1 = l1.inter(l2);
      long double x2 = l2.inter(l);
      if (x2 < x1 + EPS) {
        st.pop_back();
      } else {
        break;
      }
    }
    st.push_back(l);
  }
  long long get_best(long long x) {
    int L = -1;
    int R = ((int)(st).size()) - 1;
    while (L < R - 1) {
      int M = (L + R) / 2;
      long double xx = st[M].inter(st[M + 1]);
      if (xx < x) {
        L = M;
      } else {
        R = M;
      }
    }
    long long ans = -INF;
    for (int i = max(0, L - 1); i < min(((int)(st).size()), R + 2); ++i) {
      ans = max(ans, st[i].get(x));
    }
    return ans;
  }
};
struct Query {
  int type;
  int a, b;
  int i;
  int q;
  int id;
  bool read(int id_) {
    id = id_;
    if (scanf("%d", &type) < 1) {
      return false;
    }
    if (type == 1) {
      scanf("%d%d", &a, &b);
    } else if (type == 2) {
      scanf("%d", &i);
      --i;
    } else {
      assert(type == 3);
      scanf("%d", &q);
    }
    return true;
  }
  bool operator<(const Query& other) const {
    return make_pair(a, b) < make_pair(other.a, other.b);
  }
};
vector<Query> qs;
vector<Query> sorted_qs;
bool alive[MAXN];
int n;
bool used[MAXN];
bool read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  qs.resize(n);
  for (int i = 0; i < (int)n; ++i) {
    assert(qs[i].read(i));
  }
  return true;
}
void solve(int l, int r) {
  memset(used, false, sizeof used);
  vector<int> ids;
  for (int i = l; i <= r; ++i) {
    if (qs[i].type == 2) {
      used[qs[i].i] = true;
      ids.push_back(qs[i].i);
    }
    if (qs[i].type == 1) {
      used[qs[i].id] = true;
      ids.push_back(qs[i].id);
    }
  }
  Hull h;
  for (const auto& q : sorted_qs) {
    assert(q.type == 1);
    if (alive[q.id] && !used[q.id]) {
      h.push(Line(q.a, q.b));
    }
  }
  for (int i = l; i <= r; ++i) {
    if (qs[i].type != 3) {
      if (qs[i].type == 2) {
        alive[qs[i].i] = false;
      } else {
        alive[qs[i].id] = true;
      }
      continue;
    }
    long long ans = -INF;
    int x = qs[i].q;
    for (int j : ids) {
      assert(qs[j].type == 1);
      if (alive[j]) {
        ans = max(ans, Line(qs[j].a, qs[j].b).get(x));
      }
    }
    ans = max(ans, h.get_best(x));
    if (ans == -INF) {
      printf("EMPTY SET\n");
    } else {
      printf("%lld\n", ans);
    }
  }
}
const int K = 1500;
void solve() {
  for (const auto& q : qs) {
    if (q.type == 1) {
      sorted_qs.push_back(q);
    }
  }
  sort(begin(sorted_qs), end(sorted_qs));
  for (int l = 0; l < ((int)(qs).size()); l += K) {
    int r = min(((int)(qs).size()) - 1, l + K - 1);
    solve(l, r);
  }
}
int main() {
  while (read()) {
    solve();
  }
  return 0;
}