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;
template <class X, class Y>
void minimize(X &x, const Y &y) {
  if (x > y) x = y;
}
template <class X, class Y>
void maximize(X &x, const Y &y) {
  if (x < y) x = y;
}
template <class T>
T Abs(const T &x) {
  return (x < 0 ? -x : x);
}
const int INF = (int)1e9 + 7;
const long long LLINF = 2LL * INF * INF;
const string emptySet = "EMPTY SET";
int ceil(int b, int a) {
  while (a == 0) cout << "FUCK" << endl;
  if (a < 0) return (ceil(-b, -a));
  if (b >= 0) return (b / a + (b % a != 0));
  if (b % a == 0) return (b / a);
  return (-((-b) / a));
}
class ConvexHull {
 private:
  struct Segment {
    int x, a, b;
    Segment() { x = a = b = 0; }
    Segment(int _x, int _a, int _b) {
      x = _x;
      a = _a;
      b = _b;
    }
    long long y(void) const { return (1LL * a * x + b); }
  };
  vector<Segment> segments;

 public:
  void addLine(int a, int b) {
    while (!segments.empty() &&
           segments.back().y() <= 1LL * a * segments.back().x + b)
      segments.pop_back();
    if (segments.empty()) {
      segments.push_back(Segment(-INF, a, b));
      return;
    }
    long long x = ceil(b - segments.back().b, segments.back().a - a);
    if (x > INF) return;
    segments.push_back(Segment(x, a, b));
  }
  long long query(int x) {
    while (!segments.empty() && segments.back().x > x) segments.pop_back();
    if (segments.empty()) return (-LLINF);
    int a = segments.back().a;
    int b = segments.back().b;
    return (1LL * a * x + b);
  }
};
struct Query {
  int type, x, y, id;
  Query() { type = x = y = id = 0; }
  void input(int id) {
    this->id = id;
    scanf("%d%d", &type, &x);
    if (type == 1) scanf("%d", &y);
  }
};
pair<int, int> allLines[300300];
set<pair<pair<int, int>, int> > lines;
vector<pair<pair<int, int>, int> > recentLines;
int numQuery, curQuery, lastInsert;
bool deleted[300300];
vector<Query> queries;
vector<ConvexHull> convexHulls;
vector<int> willDelete;
vector<pair<int, int> > askQueries;
long long answer[300300];
void readNextQuery(void) {
  while (queries.size() < 2000 && curQuery < numQuery) {
    curQuery++;
    Query query;
    query.input(curQuery);
    queries.push_back(query);
  }
}
void prepareQuery(void) {
  for (__typeof((queries).begin()) it = (queries).begin();
       it != (queries).end(); it++) {
    if (it->type == 2 && it->x <= lastInsert) willDelete.push_back(it->x);
    if (it->type == 3) askQueries.push_back(make_pair(it->x, it->id));
  }
  sort((willDelete).begin(), (willDelete).end());
  for (__typeof((lines).begin()) it = (lines).begin(); it != (lines).end();
       it++) {
    if (binary_search((willDelete).begin(), (willDelete).end(), it->second))
      convexHulls.push_back(ConvexHull());
    else {
      if (convexHulls.empty()) convexHulls.push_back(ConvexHull());
      convexHulls.back().addLine(it->first.first, it->first.second);
    }
  }
}
void insertLine(const Query &q) {
  lastInsert = q.id;
  recentLines.push_back(make_pair(pair<int, int>(q.x, q.y), q.id));
  lines.insert(make_pair(pair<int, int>(q.x, q.y), q.id));
  allLines[q.id] = make_pair(q.x, q.y);
}
void deleteLine(const Query &q) {
  deleted[q.x] = true;
  int x = allLines[q.x].first;
  int y = allLines[q.x].second;
  lines.erase(make_pair(pair<int, int>(x, y), q.x));
}
void processQuery(void) {
  sort((askQueries).begin(), (askQueries).end(), greater<pair<int, int> >());
  for (__typeof((convexHulls).begin()) it = (convexHulls).begin();
       it != (convexHulls).end(); it++)
    for (__typeof((askQueries).begin()) jt = (askQueries).begin();
         jt != (askQueries).end(); jt++)
      maximize(answer[jt->second], it->query(jt->first));
  for (__typeof((queries).begin()) it = (queries).begin();
       it != (queries).end(); it++) {
    if (it->type == 3) {
      int x = it->x;
      for (__typeof((willDelete).begin()) jt = (willDelete).begin();
           jt != (willDelete).end(); jt++)
        if (!deleted[*jt]) {
          int a = allLines[*jt].first;
          int b = allLines[*jt].second;
          maximize(answer[it->id], 1LL * x * a + b);
        }
      for (__typeof((recentLines).begin()) jt = (recentLines).begin();
           jt != (recentLines).end(); jt++)
        if (!deleted[jt->second]) {
          int a = jt->first.first;
          int b = jt->first.second;
          maximize(answer[it->id], 1LL * x * a + b);
        }
      if (answer[it->id] == -LLINF) answer[it->id] = LLINF;
    }
    if (it->type == 1) insertLine(*it);
    if (it->type == 2) deleteLine(*it);
  }
}
void afterProcess(void) {
  queries.clear();
  convexHulls.clear();
  recentLines.clear();
  willDelete.clear();
  askQueries.clear();
}
void process(void) {
  scanf("%d", &numQuery);
  for (int i = (1), _b = (numQuery); i <= _b; i = i + 1) answer[i] = -LLINF;
  while (curQuery < numQuery) {
    readNextQuery();
    prepareQuery();
    processQuery();
    afterProcess();
  }
  for (int i = (1), _b = (numQuery); i <= _b; i = i + 1)
    if (answer[i] > -LLINF) {
      if (answer[i] < LLINF)
        printf("%I64d\n", answer[i]);
      else
        printf("%s\n", emptySet.c_str());
    }
}
int main(void) {
  process();
  return 0;
}