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>
long long inp() {
  char c = getchar();
  long long neg = 1;
  while (c < '0' || c > '9') {
    if (c == '-') neg = -1;
    c = getchar();
  }
  long long sum = 0;
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  return sum * neg;
}
long long ans[400010], op[400010], q[400010], k[400010], c[400010];
std::vector<std::pair<long long, long long> > vec2;
bool used[400010];
long long get(std::pair<long long, long long> a, long long x) {
  return x * a.first + a.second;
}
struct SEG_Tree {
  struct SEG {
    long long l;
    long long r;
    std::vector<std::pair<long long, long long> > vec;
    long long top;
  } t[1200000];
  void build(long long cur, long long l, long long r) {
    t[cur].l = l;
    t[cur].r = r;
    t[cur].top = 0;
    if (l == r) return;
    long long mid = (l + r) >> 1;
    build(((cur) << 1), l, mid);
    build(((cur) << 1 | 1), mid + 1, r);
  }
  void modify(long long cur, long long l, long long r,
              std::pair<long long, long long> c) {
    if (t[cur].l > r || t[cur].r < l) return;
    if (t[cur].l >= l && t[cur].r <= r) {
      bool flg = false;
      while (t[cur].top > 1 &&
             ((t[cur].vec[t[cur].top - 1].second - c.second) *
                  (t[cur].vec[t[cur].top - 1].first -
                   t[cur].vec[t[cur].top - 2].first) <=
              (t[cur].vec[t[cur].top - 2].second -
               t[cur].vec[t[cur].top - 1].second) *
                  (c.first - t[cur].vec[t[cur].top - 1].first))) {
        t[cur].top--;
        flg = true;
      }
      if (flg) t[cur].vec.resize(t[cur].top);
      t[cur].top++;
      t[cur].vec.push_back(c);
      return;
    }
    modify(((cur) << 1), l, r, c);
    modify(((cur) << 1 | 1), l, r, c);
  }
  long long query(long long cur, long long x, long long c, long long ans) {
    long long l = 0;
    long long r = t[cur].top - 1;
    while (l < r) {
      long long mid = (l + r) >> 1;
      if (get(t[cur].vec[mid], c) <= get(t[cur].vec[mid + 1], c))
        l = mid + 1;
      else
        r = mid;
    }
    if (t[cur].top) ans = std::max(ans, get(t[cur].vec[l], c));
    if (t[cur].l == t[cur].r) return ans;
    return x <= t[((cur) << 1)].r ? query(((cur) << 1), x, c, ans)
                                  : query(((cur) << 1 | 1), x, c, ans);
  }
} t;
struct Node {
  std::pair<long long, long long> c;
  long long l;
  long long r;
};
std::vector<Node> mds;
bool cmp(Node a, Node b) { return a.c < b.c; }
signed main() {
  long long n = inp();
  t.build(1, 1, n);
  for (long long i = 1; i <= n; i++) {
    op[i] = inp();
    if (op[i] == 1) {
      k[i] = inp();
      c[i] = inp();
    } else if (op[i] == 2) {
      long long x = inp();
      mds.push_back((Node){std::make_pair(k[x], c[x]), x, i - 1});
      used[x] = true;
    } else
      q[i] = inp();
  }
  for (long long i = 1; i <= n; i++)
    if (op[i] == 1 && !used[i])
      mds.push_back((Node){std::make_pair(k[i], c[i]), i, n});
  std::sort(mds.begin(), mds.end(), cmp);
  for (long long i = 0; i < mds.size(); i++)
    t.modify(1, mds[i].l, mds[i].r, mds[i].c);
  for (long long i = 1; i <= n; i++) {
    if (op[i] == 3) {
      long long ans = t.query(1, i, q[i], -2e18);
      if (ans == -2e18)
        printf("EMPTY SET\n");
      else
        printf("%lld\n", t.query(1, i, q[i], -2e18));
    }
  }
}