12876번 - 반평면 땅따먹기 2

문제

원소가 하나도 없는 공집합 상태의 정수 쌍들(pairs of integers) 집합이 있을 때, n개의 연산이 주어진다. 각 연산은 세 가지 유형 중 하나이다.

1. 정수 쌍 (a, b)를 집합에 추가
2. i번째 연산에서 추가했던 정수 쌍을 집합에서 제거
3. 주어지는 정수 x에 대하여 집합에 남아있는 모든 원소 (a, b) 중 ax+b의 최댓값을 출력

주어진 연산을 수행하는 프로그램을 작성해보자.

입력

첫째 줄에 연산의 개수를 나타내는 n 이 주어집니다. (1 ≤ n ≤ 300,000)

둘째 줄부터 n개의 줄은 연산의 종류를 알려주는 하나의 정수 Type(1, 2, 3 중 하나)으로 시작한다.

Type이 1이라면, 연산 1에 해당하는 2개의 정수 a, b가 주어진다. (-10⁹ ≤ a, b ≤ 10⁹)

Type이 2라면, 연산 2에 해당하는 1개의 정수 i(1 ≤ i ≤ n)가 주어진다. i는 해당 연산의 번호보다 작고, i번째 연산은 1번 연산이며 해당 연산으로 추가된 정수 쌍은 이전에 또 제거된 적이 없다.

Type이 3이라면, 연산 3에 해당하는 1개의 정수 x가 주어진다. (-10⁹ ≤ x ≤ 10⁹)

출력

연산 3을 수행할 때마다 답을 순서대로 한 줄에 하나씩 출력한다. 만약 정수 쌍들의 집합이 공집합이라면 “EMPTY”를 출력한다. (따옴표 제외)

제한

힌트