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;
inline int in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
const int maxn = 5e5 + 10;
const int maxm = 5e5 + 10;
const int mod = 1e9 + 7;
const long long infll = 2e18 + 10;
const int inf = 1e9;
struct Str {
  int a, b;
  inline long long value(int x) { return 1LL * a * x + b; }
} Line[maxn];
vector<int> Queries[maxn];
vector<pair<int, int> > events[maxn];
int cur = 0;
bool mark[maxn];
int q[maxn];
inline int when(int a, int b) {
  if (Line[a].a <= Line[b].a) return inf;
  int ret = (Line[b].b - Line[a].b) / (Line[a].a - Line[b].a);
  if (Line[a].value(ret) <= Line[b].value(ret)) ret++;
  return ret;
}
inline void do_job(int id) {
  int t = 0;
  for (auto x : Queries[id])
    if (!mark[x]) q[t++] = x;
  sort(q, q + t, [](const int &a, const int &b) {
    return Line[a].value(-inf) > Line[b].value(-inf);
  });
  events[id].clear();
  if (t == 0) return;
  events[id].push_back({-inf, q[0]});
  for (int _ = 1; _ < t; _++) {
    int i = q[_];
    while (events[id].size() >= 2 &&
           when(i, events[id].back().second) <= events[id].back().first)
      events[id].pop_back();
    int hit = when(i, events[id].back().second);
    if (hit - inf) events[id].push_back({hit, i});
  }
  events[id].shrink_to_fit();
}
const int LIM = 500;
int where[maxn];
int32_t main() {
  int q = in();
  int tot = 0;
  for (int _ = 0; _ < q; _++) {
    int tp = in();
    if (tp == 1) {
      tot++;
      Line[_].a = in(), Line[_].b = in();
      where[_] = cur;
      Queries[cur].push_back(_);
      if (Queries[cur].size() >= LIM) {
        do_job(cur);
        cur++;
      }
    } else if (tp == 2) {
      tot--;
      int id = in() - 1;
      mark[id] = true;
      if (Queries[where[id]].size() == LIM) do_job(where[id]);
    } else {
      int x = in();
      if (tot == 0) {
        printf("EMPTY SET\n");
        continue;
      }
      long long ret = -infll;
      for (int i = 0; i < cur; i++) {
        if (!events[i].size()) continue;
        int upp =
            upper_bound(events[i].begin(), events[i].end(), make_pair(x, inf)) -
            events[i].begin();
        upp--;
        assert(!mark[events[i][upp].second]);
        ret = max(ret, Line[events[i][upp].second].value(x));
      }
      for (auto id : Queries[cur]) {
        if (mark[id]) continue;
        ret = max(ret, Line[id].value(x));
      }
      printf("%lld\n", ret);
    }
  }
}