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;
constexpr int N = 300005;
struct convex_hull {
  struct line {
    long long a, b;
    line(long long _a = 0, long long _b = 0) { a = _a, b = _b; }
    long long f(int x) { return a * x + b; }
  };
  using float_type = __int128_t;
  float_type one = 1;
  bool bad(const line &ln1, const line &ln2, const line &ln3) {
    return one * (ln2.b - ln1.b) * (ln3.a - ln1.a) <=
           one * (ln3.b - ln1.b) * (ln2.a - ln1.a);
  }
  vector<line> v;
  int size() { return v.size(); }
  void insert(long long a, long long b) {
    line ln(a, b);
    while (v.size() > 1 && v.back().a == a) v.pop_back();
    while (v.size() > 1 && bad(v[v.size() - 2], v.back(), ln)) v.pop_back();
    v.push_back(ln);
  }
  long long query(int x) {
    if (v.size() == 0) return LLONG_MIN >> 1;
    int l = 0, r = ((int)v.size()) - 2;
    long long ret = LLONG_MIN >> 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (v[mid].f(x) > v[mid + 1].f(x))
        ret = v[mid].f(x), r = mid - 1;
      else
        l = mid + 1;
    }
    return max(ret, v.back().f(x));
  }
} ch[N << 2];
namespace IO {
const int BUFFER_SIZE = 1 << 15;
char input_buffer[BUFFER_SIZE];
size_t input_pos = 0, input_len = 0;
char output_buffer[BUFFER_SIZE];
int output_pos = 0;
char number_buffer[100];
uint8_t lookup[100];
void _update_input_buffer() {
  input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
  input_pos = 0;
  if (input_len == 0) input_buffer[0] = EOF;
}
inline char next_char(bool advance = true) {
  if (input_pos >= input_len) _update_input_buffer();
  return input_buffer[advance ? input_pos++ : input_pos];
}
inline bool isspace(char c) {
  return (unsigned char)(c - '\t') < 5 || c == ' ';
}
inline void read_char(char &c) {
  while (isspace(next_char(false))) next_char();
  c = next_char();
}
template <typename T>
inline void read_int(T &number) {
  bool negative = false;
  number = 0;
  while (!isdigit(next_char(false)))
    if (next_char() == '-') negative = true;
  do {
    number = 10 * number + (next_char() - '0');
  } while (isdigit(next_char(false)));
  if (negative) number = -number;
}
template <typename T, typename... Args>
inline void read_int(T &number, Args &...args) {
  read_int(number);
  read_int(args...);
}
inline void read_str(string &str) {
  while (isspace(next_char(false))) next_char();
  str.clear();
  do {
    str += next_char();
  } while (!isspace(next_char(false)));
}
void _flush_output() {
  fwrite(output_buffer, sizeof(char), output_pos, stdout);
  output_pos = 0;
}
inline void write_char(char c) {
  if (output_pos == BUFFER_SIZE) _flush_output();
  output_buffer[output_pos++] = c;
}
template <typename T>
inline void write_int(T number, char after = '\0') {
  if (number < 0) {
    write_char('-');
    number = -number;
  }
  int length = 0;
  while (number >= 10) {
    uint8_t lookup_value = lookup[number % 100];
    number /= 100;
    number_buffer[length++] = char((lookup_value & 15) + '0');
    number_buffer[length++] = char((lookup_value >> 4) + '0');
  }
  if (number != 0 || length == 0) write_char(char(number + '0'));
  for (int i = length - 1; i >= 0; i--) write_char(number_buffer[i]);
  if (after) write_char(after);
}
inline void write_str(const string &str, char after = '\0') {
  for (char c : str) write_char(c);
  if (after) write_char(after);
}
void init() {
  bool exit_success = atexit(_flush_output) == 0;
  assert(exit_success);
  for (int i = 0; i < 100; i++) lookup[i] = uint8_t((i / 10 << 4) + i % 10);
}
}  // namespace IO
int n, t[N], q[N], e[N];
pair<int, int> z[N];
vector<pair<int, int>> pending[N << 2];
void insert(int id, int l, int r, int L, int R, pair<int, int> &pp) {
  if (L > r || l > R) return;
  if (L <= l && r <= R) {
    pending[id].push_back(pp);
    return;
  }
  insert(id << 1, l, ((l + r) >> 1), L, R, pp);
  insert(id << 1 | 1, ((l + r) >> 1) + 1, r, L, R, pp);
}
void query(int id, int l, int r, int pos, int X, long long &ans) {
  if (ch[id].size() > 0) ans = max(ans, ch[id].query(X));
  if (l == r) return;
  if (pos <= ((l + r) >> 1))
    query(id << 1, l, ((l + r) >> 1), pos, X, ans);
  else
    query(id << 1 | 1, ((l + r) >> 1) + 1, r, pos, X, ans);
}
void solution() {
  IO::init();
  IO::read_int(n);
  fill(e, e + N, n);
  for (int i = 1; i <= n; i++) {
    IO::read_int(t[i]);
    if (t[i] == 1)
      IO::read_int(z[i].first, z[i].second);
    else if (t[i] == 2) {
      int u;
      IO::read_int(u);
      e[u] = i;
    } else
      IO::read_int(q[i]);
  }
  for (int i = 1; i <= n; i++)
    if (t[i] == 1) {
      insert(1, 1, n, i, e[i], z[i]);
    }
  for (int i = 1; i <= (n << 2); i++) {
    if (pending[i].size() == 0) continue;
    sort(pending[i].begin(), pending[i].end());
    for (pair<int, int> &pp : pending[i]) ch[i].insert(pp.first, pp.second);
  }
  for (int i = 1; i <= n; i++)
    if (t[i] == 3) {
      long long ans = LLONG_MIN;
      query(1, 1, n, i, q[i], ans);
      if (ans == LLONG_MIN)
        cout << "EMPTY SET\n";
      else
        cout << ans << "\n";
    }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int tc = 1;
  while (tc--) {
    solution();
    cout << '\n';
  }
}