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 = 300010;
const long long INF = 2e18;
int t[maxn];
long long a[maxn];
long long b[maxn];
bool ban[maxn];
long long ans[maxn];
long long ans2[maxn];
struct Point {
  long long x, y;
  Point(long long x, long long y) : x(x), y(y) {}
  Point() {}
  bool operator<(const Point &other) const {
    if (x != other.x) {
      return x < other.x;
    }
    return y > other.y;
  }
};
Point ch[maxn];
pair<Point, int> ppi[maxn];
int sz;
int n;
int k;
void ConvexHull(int end) {
  sz = 0;
  Point pre = Point(-INF, -INF);
  for (int i = 0; i < k; i++) {
    Point pt = ppi[i].first;
    if (ban[ppi[i].second] || ppi[i].second > end) {
      continue;
    }
    if (pt.x == pre.x) {
      continue;
    }
    pre = pt;
    if (sz < 2) {
      ch[sz++] = pt;
    } else {
      while (sz >= 2 &&
             (pt.y - ch[sz - 1].y) * (ch[sz - 1].x - ch[sz - 2].x) >=
                 (ch[sz - 1].y - ch[sz - 2].y) * (pt.x - ch[sz - 1].x)) {
        sz--;
      }
      ch[sz++] = pt;
    }
  }
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &t[i]);
    if (t[i] == 1) {
      scanf("%I64d%I64d", &a[i], &b[i]);
      ppi[k++] = make_pair(Point(a[i], b[i]), i);
    } else {
      scanf("%I64d", &a[i]);
    }
    ans[i] = ans2[i] = -INF;
  }
  sort(ppi, ppi + k);
  int LEN = sqrt(n);
  Point pt_in_block[555];
  pair<long long, int> query_in_block[555];
  int cntq = 0;
  int k = 0;
  for (int s = 1; s <= n; s += LEN) {
    int e = min(n + 1, s + LEN);
    cntq = 0;
    for (int i = s; i < e; i++) {
      if (t[i] == 3) {
        for (int j = s; j < e; j++) {
          if (t[j] == 1 && j < i && !ban[j]) {
            ans[i] = max(ans[i], b[j] + a[j] * a[i]);
          } else if (t[j] == 2 && j > i && a[j] < i) {
            int aa = a[a[j]];
            int bb = b[a[j]];
            ans[i] = max(ans[i], bb + aa * a[i]);
          }
        }
        query_in_block[cntq++] = make_pair(a[i], i);
      } else if (t[i] == 2) {
        ban[a[i]] = 1;
      }
    }
    sort(query_in_block, query_in_block + cntq);
    ConvexHull(s - 1);
    if (sz != 0) {
      int pos = 0;
      for (int i = 0; i < cntq; i++) {
        while (pos < sz) {
          long long val = ch[pos].y + query_in_block[i].first * ch[pos].x;
          if (val > ans2[query_in_block[i].second]) {
            ans2[query_in_block[i].second] = val;
          } else {
            if (pos) {
              pos--;
            }
            break;
          }
          pos++;
          if (pos == sz) {
            if (pos) pos--;
            break;
          }
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (t[i] == 3) {
      long long a = max(ans[i], ans2[i]);
      if (a == -INF) {
        printf("EMPTY SET\n");
      } else {
        printf("%I64d\n", a);
      }
    }
  }
  return 0;
}