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 N = 3e5 + 5;
const long long inf = 9000000000000000000;
const long long xiinf = 1e9 + 5;
long long n, dui[N], cnt, cnt1, ma[N << 2], pan[N], h[N << 2], t[N << 2], cnt2,
    gudan, ans[N];
struct pigu {
  long long x, y, l, r;
} a[N];
struct xunwen {
  long long k, t, id;
} wen[N], wen1[N];
inline long long cmp(pigu x, pigu y) { return x.x < y.x; }
inline long long cmp1(xunwen x, xunwen y) { return x.k < y.k; }
inline long long cmp2(xunwen x, xunwen y) { return x.k > y.k; }
inline long long cmp3(pigu x, pigu y) { return x.x > y.x; }
inline long long read() {
  char c = getchar();
  long long x = 0, f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar();
  }
  return x * f;
}
vector<long long> que[N << 2];
inline void build(long long now, long long l, long long r) {
  ma[now] = -inf;
  h[now] = 0;
  t[now] = -1;
  que[now].clear();
  if (l == r) return;
  long long mid = (l + r) >> 1;
  build(now << 1, l, mid);
  build(now << 1 | 1, mid + 1, r);
}
inline long long suan(long long x, long long y) {
  long long l = 1, r = xiinf, daan = xiinf;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    if (mid * a[x].x + a[x].y >= mid * a[y].x + a[y].y)
      r = mid - 1, daan = mid;
    else
      l = mid + 1;
  }
  return daan;
}
inline long long suan1(long long x, long long y) {
  long long l = -xiinf, r = -1, daan = -xiinf;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    if (mid * a[x].x + a[x].y >= mid * a[y].x + a[y].y)
      l = mid + 1, daan = mid;
    else
      r = mid - 1;
  }
  return daan;
}
inline void update(long long now, long long l, long long r, long long L,
                   long long R, long long x) {
  if (l >= L && r <= R) {
    ma[now] = max(ma[now], a[x].y);
    while (que[now].size() < t[now] + 5) que[now].push_back(0);
    while (h[now] < t[now] &&
           (a[x].y >= a[que[now][t[now]]].y ||
            suan(x, que[now][t[now]]) <=
                suan(que[now][t[now]], que[now][t[now] - 1])))
      t[now]--;
    que[now][++t[now]] = x;
    return;
  }
  long long mid = (l + r) >> 1;
  if (L <= mid) update(now << 1, l, mid, L, R, x);
  if (R >= mid + 1) update(now << 1 | 1, mid + 1, r, L, R, x);
}
inline void query(long long now, long long l, long long r, long long zai,
                  long long x) {
  if (x == 0)
    gudan = max(gudan, ma[now]);
  else {
    while (h[now] < t[now] && suan(que[now][h[now] + 1], que[now][h[now]]) <= x)
      h[now]++;
    if (h[now] <= t[now])
      gudan = max(gudan, x * a[que[now][h[now]]].x + a[que[now][h[now]]].y);
  }
  if (l == r) return;
  long long mid = (l + r) >> 1;
  if (zai <= mid)
    query(now << 1, l, mid, zai, x);
  else
    query(now << 1 | 1, mid + 1, r, zai, x);
}
inline void update1(long long now, long long l, long long r, long long L,
                    long long R, long long x) {
  if (l >= L && r <= R) {
    ma[now] = max(ma[now], a[x].y);
    while (que[now].size() < t[now] + 5) que[now].push_back(0);
    while (h[now] < t[now] &&
           (a[x].y >= a[que[now][t[now]]].y ||
            suan1(x, que[now][t[now]]) >=
                suan1(que[now][t[now]], que[now][t[now] - 1])))
      t[now]--;
    que[now][++t[now]] = x;
    return;
  }
  long long mid = (l + r) >> 1;
  if (L <= mid) update1(now << 1, l, mid, L, R, x);
  if (R >= mid + 1) update1(now << 1 | 1, mid + 1, r, L, R, x);
}
inline void query1(long long now, long long l, long long r, long long zai,
                   long long x) {
  if (x == 0)
    gudan = max(gudan, ma[now]);
  else {
    while (h[now] < t[now] &&
           suan1(que[now][h[now] + 1], que[now][h[now]]) >= x)
      h[now]++;
    if (h[now] <= t[now])
      gudan = max(gudan, x * a[que[now][h[now]]].x + a[que[now][h[now]]].y);
  }
  if (l == r) return;
  long long mid = (l + r) >> 1;
  if (zai <= mid)
    query1(now << 1, l, mid, zai, x);
  else
    query1(now << 1 | 1, mid + 1, r, zai, x);
}
signed main() {
  n = read();
  for (long long i = 1, x, y, opt; i <= n; i++) {
    opt = read();
    if (opt == 1) {
      x = read();
      y = read();
      a[++cnt].x = x;
      a[cnt].y = y;
      a[cnt].l = i;
      dui[i] = cnt;
    }
    if (opt == 2) {
      x = read();
      a[dui[x]].r = i - 1;
    }
    if (opt == 3) {
      x = read();
      pan[i] = 1;
      if (x > 0)
        wen[++cnt1].k = x, wen[cnt1].t = i, wen[cnt1].id = i;
      else
        wen1[++cnt2].k = x, wen1[cnt2].t = i, wen1[cnt2].id = i;
    }
  }
  sort(a + 1, a + cnt + 1, cmp);
  sort(wen + 1, wen + cnt1 + 1, cmp1);
  sort(wen1 + 1, wen1 + cnt2 + 1, cmp2);
  build(1, 1, n);
  for (long long i = 1; i <= cnt; i++)
    update(1, 1, n, a[i].l, a[i].r ? a[i].r : n, i);
  for (long long i = 1; i <= cnt1; i++) {
    gudan = -inf;
    query(1, 1, n, wen[i].t, wen[i].k);
    ans[wen[i].id] = gudan;
  }
  sort(a + 1, a + cnt + 1, cmp3);
  build(1, 1, n);
  for (long long i = 1; i <= cnt; i++)
    update1(1, 1, n, a[i].l, a[i].r ? a[i].r : n, i);
  for (long long i = 1; i <= cnt2; i++) {
    gudan = -inf;
    query1(1, 1, n, wen1[i].t, wen1[i].k);
    ans[wen1[i].id] = gudan;
  }
  for (long long i = 1; i <= n; i++)
    if (pan[i]) ans[i] == -inf ? cout << "EMPTY SET\n" : cout << ans[i] << "\n";
  return 0;
}