우선순위 큐(Priority Queue)는 가장 우선순위가 높은 하나의 원소만 빠르게 다룰 수 있다.

이번에는 최댓값과 최솟값을 모두 빠르게 찾아내고 삭제할 수 있는 "이중 우선순위 큐(Double-Ended Priority Queue)"를 구현하고자 한다.

비어 있는 이중 우선순위 큐에서 시작하여 \(N\)개의 명령을 처리하는 프로그램을 작성하시오.

명령의 종류는 다음과 같이 세 가지이다.

• 1 x: 정수 \(x\)를 큐에 삽입한다. (동일한 정수가 여러 번 삽입될 수 있다.)
• 2 1: 현재 큐에 있는 원소 중 최댓값을 삭제한다. 최댓값이 여러 개라면 그중 하나만 삭제한다. 만약 큐가 비어 있다면 이 명령은 무시한다.
• 2 -1: 현재 큐에 있는 원소 중 최솟값을 삭제한다. 최솟값이 여러 개라면 그중 하나만 삭제한다. 만약 큐가 비어 있다면 이 명령은 무시한다.
• 3: 현재 큐에 남아있는 최댓값과 최솟값을 공백으로 구분하여 한 줄에 출력한다. 만약 큐가 비어 있다면 EMPTY를 출력한다.

입력

첫째 줄에 명령의 수 \(N\)이 주어진다.

둘째 줄부터 \(N\)개의 줄에 명령이 하나씩 주어진다.

출력

3번 명령이 주어질 때마다 해당 명령의 결과를 한 줄에 하나씩 출력한다.

제한사항

• \(1 \le N \le 100000\)
• \(1\)번 명령으로 입력되는 정수 \(x\)는 \(-2 \times 10^9 \le x \le 2 \times 10^9\) 범위의 정수이다.
• \(3\)번 명령은 최소 하나 이상 주어진다.

예제 입력 1

8
1 10
1 20
1 10
3
2 1
3
2 -1
3

예제 출력 1

20 10
10 10
10 10