F. Лена и запросы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лена — программист. На работе она получила задачу.

Рассмотрим некоторое, изначально пустое множество пар целых чисел. Лене нужно обработать n запросов одного из трёх типов:

  1. Добавить пару чисел (a, b) в множество.
  2. Удалить пару чисел, добавленную в i-м запросе. Все запросы пронумерованы целыми числами от 1 до n.
  3. Для заданного целого числа q найти максимальное значение величины x·q + y среди всех пар (x, y) из множества.

Помогите Лене обработать запросы.

Входные данные

В первой строке находится целое число n (1 ≤ n ≤ 3·105) — количество запросов.

Каждая из следующих n строк начинается с целого числа t (1 ≤ t ≤ 3) — типа очередного запроса.

Далее в запросах первого типа следует пара целых чисел a и b ( - 109 ≤ a, b ≤ 109).

В запросах второго типа следует целое число i (1 ≤ i ≤ n). Гарантируется, что число i меньше номера текущего запроса, i-й запрос первого типа и пара из i-го запроса ещё не удалена.

В запросах третьего типа следует целое число q ( - 109 ≤ q ≤ 109).

Выходные данные

Для запросов третьего типа выведите в отдельной строке искомое максимальное значение x·q + y.

Если в множестве нет пар выведите "EMPTY SET".

Пример
Входные данные
7
3 1
1 2 3
3 1
1 -1 100
3 1
2 4
3 1
Выходные данные
EMPTY SET
5
99
5