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;
struct Point {
  long long x, y;
  Point() {}
  Point(long long a, long long b) : x(a), y(b) {}
  Point operator-(Point b) { return Point(x - b.x, y - b.y); }
  bool operator<(const Point& b) const {
    return (x != b.x) ? x < b.x : y < b.y;
  }
};
inline long long cross(Point x, Point y) { return x.x * y.y - x.y * y.x; }
vector<Point> vt[1200000];
Point p[300005];
int top;
void build(vector<Point> a) {
  top = 0;
  sort(a.begin(), a.end());
  for (int i = 0; i < a.size(); i++) {
    while (top > 1 && cross(a[i] - p[top - 1], p[top] - p[top - 1]) <= 0) top--;
    p[++top] = a[i];
  }
}
void update(int l, int r, int o, int lx, int rx, Point p) {
  if (l >= lx && r <= rx)
    vt[o].push_back(p);
  else {
    int m = ((l + r) >> 1);
    if (m >= lx) update(l, m, o * 2, lx, rx, p);
    if (m < rx) update(m + 1, r, o * 2 + 1, lx, rx, p);
  }
}
long long ans[300005], q[300005];
bool in[300005];
inline long long getsum(Point x, long long q) { return x.x * q + x.y; }
long long solve(long long q) {
  int l = 1, r = top;
  while (r - l > 2) {
    int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
    if (getsum(p[m1], q) > getsum(p[m2], q))
      r = m2;
    else
      l = m1;
  }
  long long ans = -(long long)(2e18);
  for (int i = l; i <= r; i++) ans = max(ans, getsum(p[i], q));
  return ans;
}
void query(int l, int r, int o) {
  build(vt[o]);
  for (int i = l; i <= r; i++)
    if (in[i]) ans[i] = max(ans[i], solve(q[i]));
  if (l == r) return;
  int m = ((l + r) >> 1);
  query(l, m, o * 2);
  query(m + 1, r, o * 2 + 1);
}
Point ope[300005];
bool vis[300005];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int kind;
    scanf("%d", &kind);
    if (kind == 1) {
      int x, y;
      scanf("%d%d", &x, &y);
      ope[i] = Point(x, y);
      vis[i] = 1;
    } else if (kind == 2) {
      int x;
      scanf("%d", &x);
      if (vis[x]) update(1, n, 1, x, i - 1, ope[x]);
      vis[x] = 0;
    } else {
      scanf("%lld", &q[i]);
      in[i] = 1;
    }
  }
  for (int i = 1; i <= n; i++)
    if (vis[i]) update(1, n, 1, i, n, ope[i]);
  for (int i = 1; i <= n; i++) ans[i] = -(long long)(2e18);
  query(1, n, 1);
  for (int i = 1; i <= n; i++)
    if (in[i]) {
      if (ans[i] == -(long long)(2e18))
        puts("EMPTY SET");
      else
        printf("%lld\n", ans[i]);
    }
  return 0;
}