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;
template <typename Tp>
Tp &read(Tp &x) {
  static char c, f;
  for (f = 0; !isdigit(c = getchar());) f |= (c == '-');
  for (x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  return f ? x = -x : x;
}
template <typename Tp>
Tp read() {
  Tp x;
  return read(x);
}
struct Point {
  int x, y;
  Point() {}
  Point(const int &x, const int &y) : x(x), y(y) {}
  Point operator-(const Point &rhs) const {
    return Point(x - rhs.x, y - rhs.y);
  }
  bool operator<(const Point &rhs) const {
    if (x != rhs.x) return x < rhs.x;
    return y < rhs.y;
  }
};
long long Cross(const Point &a, const Point &b) {
  return (long long)a.x * b.y - (long long)a.y * b.x;
}
long long Dot(const Point &a, const Point &b) {
  return (long long)a.x * b.x + (long long)a.y * b.y;
}
const int N = 300000 + 10;
const long long INF = ~0ull >> 1;
Point p[N];
bool cmp_up(const Point &a, const Point &b) {
  if (a.x != b.x) return a.x < b.x;
  return a.y < b.y;
}
bool cmp_down(const Point &a, const Point &b) {
  if (a.x != b.x) return a.x > b.x;
  return a.y > b.y;
}
bool cmpk(const Point &a, const Point &b) { return Cross(a, b) < 0; }
long long ans[N];
int fuck[N], type[N], pid[N];
void merge_sort(int (&s)[N], int l, int r,
                bool cmp(const Point &, const Point &)) {
  static int tmp[N];
  int mid = (l + r) >> 1;
  int m = l, c1 = l, c2 = mid + 1;
  while (1) {
    while (c1 <= mid && !type[s[c1]]) c1++;
    while (c2 <= r && !type[s[c2]]) c2++;
    if (c1 > mid && c2 > r) break;
    if (c1 <= mid && (c2 > r || cmp(p[pid[s[c1]]], p[pid[s[c2]]])))
      tmp[m++] = s[c1++];
    else
      tmp[m++] = s[c2++];
  }
  c1 = l, c2 = mid + 1;
  while (1) {
    while (c1 <= mid && type[s[c1]]) c1++;
    while (c2 <= r && type[s[c2]]) c2++;
    if (c1 > mid && c2 > r) break;
    if (c1 <= mid && (c2 > r || cmpk(p[pid[s[c1]]], p[pid[s[c2]]])))
      tmp[m++] = s[c1++];
    else
      tmp[m++] = s[c2++];
  }
  for (int i = l; i <= r; i++) s[i] = tmp[i];
}
void solve1(int (&s)[N], int l, int r, bool cmp(const Point &, const Point &)) {
  if (l >= r) return;
  static int ch[N];
  int mid = (l + r) >> 1;
  solve1(s, l, mid, cmp);
  solve1(s, mid + 1, r, cmp);
  int m = 0;
  for (int i = l; i <= mid; i++) {
    int cur = pid[s[i]];
    if (type[s[i]] != 1) continue;
    while (m > 1 && Cross(p[ch[m - 2]] - p[cur], p[ch[m - 1]] - p[cur]) >= 0)
      m--;
    ch[m++] = cur;
  }
  int cur = 0;
  for (int i = mid + 1; i <= r; i++) {
    if (type[s[i]]) continue;
    while (cur + 1 < m &&
           Dot(p[ch[cur + 1]], p[pid[s[i]]]) > Dot(p[ch[cur]], p[pid[s[i]]]))
      cur++;
    if (cur < m) ans[s[i]] = max(ans[s[i]], Dot(p[ch[cur]], p[pid[s[i]]]));
  }
  merge_sort(s, l, r, cmp);
}
void solve2(int (&s)[N], int l, int r, bool cmp(const Point &, const Point &)) {
  if (l >= r) return;
  int mid = (l + r) >> 1;
  static int flag[N], clk = 0;
  ++clk;
  for (int i = l; i <= mid; i++) {
    if (type[s[i]] == -1) {
      type[fuck[pid[s[i]]]] = -2;
    } else if (type[s[i]] == 0) {
      type[s[i]] = -3;
    } else
      flag[s[i]] = clk;
  }
  for (int i = mid + 1; i <= r; i++) {
    if (type[s[i]]) {
      if (type[s[i]] == -1) {
        type[fuck[pid[s[i]]]] = -2;
        if (flag[fuck[pid[s[i]]]] == clk) {
          type[s[i]] = 1;
        }
      } else
        type[s[i]] = -2;
    }
  }
  static int tmp[N];
  for (int i = l; i <= r; i++) tmp[i] = s[i];
  reverse(s + mid + 1, s + r + 1);
  solve1(s, l, r, cmp);
  for (int i = l; i <= r; i++) s[i] = tmp[i];
  for (int i = l; i <= mid; i++) {
    if (type[s[i]] == -1) {
      type[fuck[pid[s[i]]]] = 1;
    } else if (type[s[i]] == -3) {
      type[s[i]] = 0;
    }
  }
  for (int i = mid + 1; i <= r; i++) {
    if (type[s[i]] == 1)
      type[fuck[pid[s[i]]]] = 1, type[s[i]] = -1;
    else if (type[s[i]] == -2)
      type[s[i]] = 1;
  }
  solve2(s, l, mid, cmp);
  solve2(s, mid + 1, r, cmp);
}
map<Point, int> mp;
multiset<int> fuck2;
int main() {
  static int id[N];
  int n;
  int ty;
  while (scanf("%d", &n) == 1 && n) {
    int tot_p = 0;
    Point curp;
    for (int i = 0, j; i < n; i++) {
      ans[i] = -INF;
      read(ty);
      if (ty == 1) {
        type[i] = 1;
        read(curp.x), read(curp.y);
      } else if (ty == 2) {
        type[i] = -1;
        read(j);
        curp = p[pid[j - 1]];
      } else if (ty == 3) {
        type[i] = 0;
        read(curp.x);
        curp.y = 1;
      }
      if (type[i] == -1)
        pid[i] = mp[curp], fuck2.erase(fuck2.find(curp.x));
      else {
        if (type[i] == 1)
          mp[curp] = tot_p, fuck[tot_p] = i, fuck2.insert(curp.x);
        else if (!curp.y)
          ans[i] = max((long long)*--fuck2.end() * curp.x,
                       (long long)*fuck2.begin() * curp.x);
        pid[i] = tot_p, p[tot_p++] = curp;
      }
    }
    int m = 0;
    for (int i = 0; i < n; i++) {
      if (!type[i] && p[pid[i]].y <= 0) continue;
      id[m++] = i;
    }
    solve2(id, 0, m - 1, cmp_up);
    m = 0;
    for (int i = 0; i < n; i++) {
      if (!type[i] && p[pid[i]].y >= 0) continue;
      id[m++] = i;
    }
    solve2(id, 0, m - 1, cmp_down);
    for (int i = 0; i < n; i++) {
      if (!type[i]) {
        if (ans[i] == -INF)
          puts("EMPTY SET");
        else
          printf("%I64d\n", ans[i]);
      }
    }
  }
  return 0;
}