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 = 3e5 + 5;
int n;
struct P {
  long long x, y;
};
bool operator<(const P &a, const P &b) {
  return a.x == b.x ? a.y < b.y : a.x < b.x;
}
P operator-(P a, P b) { return (P){a.x - b.x, a.y - b.y}; }
long long operator*(P a, P b) { return a.x * b.y - a.y * b.x; }
long long operator^(P a, P b) { return a.x * b.x + a.y * b.y; }
struct CH {
  vector<P> ch;
  void add(P p) { ch.push_back(p); }
  void build() {
    vector<P> tmp;
    tmp = ch;
    sort(tmp.begin(), tmp.end());
    ch.clear();
    for (int i = 0; i < tmp.size(); i++) {
      while (ch.size() > 1 &&
             (tmp[i] - ch.back()) * (ch.back() - ch[ch.size() - 2]) <= 0)
        ch.pop_back();
      ch.push_back(tmp[i]);
    }
  }
  long long Qmax(P p) {
    int l = 0, r = ch.size() - 1;
    if (ch.empty()) return LLONG_MIN;
    while (r - l > 2) {
      int mid1 = l + (r - l) / 3;
      int mid2 = r - (r - l) / 3;
      if ((p ^ ch[mid1]) > (p ^ ch[mid2]))
        r = mid2;
      else
        l = mid1;
    }
    long long ans = LLONG_MIN;
    for (int i = l; i <= r; i++) ans = max(ans, p ^ ch[i]);
    return ans;
  }
};
int lef[maxn], rig[maxn];
P po[maxn];
vector<pair<int, int> > Q;
CH t[maxn << 2];
void Add(int o, int l, int r, int l0, int r0, P p) {
  if (l0 <= l && r0 >= r) {
    t[o].add(p);
    return;
  }
  int mid = (l + r) / 2;
  if (l0 <= mid) Add(o << 1, l, (l + r) / 2, l0, r0, p);
  if (r0 > mid) Add(o << 1 | 1, (l + r) / 2 + 1, r, l0, r0, p);
}
void build(int o, int l, int r) {
  t[o].build();
  if (l == r) return;
  build(o << 1, l, (l + r) / 2);
  build(o << 1 | 1, (l + r) / 2 + 1, r);
}
long long Qmax(int o, int l, int r, int l0, int r0, P p) {
  long long ans = t[o].Qmax(p);
  if (l0 <= l && r0 >= r) return ans;
  int mid = (l + r) >> 1;
  if (l0 <= mid) ans = max(ans, Qmax(o << 1, l, (l + r) / 2, l0, r0, p));
  if (r0 > mid) ans = max(ans, Qmax(o << 1 | 1, (l + r) / 2 + 1, r, l0, r0, p));
  return ans;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int x, y;
      scanf("%d%d", &x, &y);
      lef[i] = i;
      rig[i] = n;
      po[i] = (P){x, y};
    } else if (t == 2) {
      int id;
      scanf("%d", &id);
      rig[id] = i;
    } else {
      int q;
      scanf("%d", &q);
      Q.push_back(make_pair(i, q));
    }
  }
  for (int i = 1; i <= n; i++)
    if (lef[i]) Add(1, 1, n, lef[i], rig[i], po[i]);
  build(1, 1, n);
  for (int i = 0; i < Q.size(); i++) {
    long long ans = Qmax(1, 1, n, Q[i].first, Q[i].first, (P){Q[i].second, 1});
    if (ans == LLONG_MIN)
      puts("EMPTY SET");
    else
      printf("%I64d\n", ans);
  }
  return 0;
}