이중 우선순위 큐

이중 우선순위 큐(Double-Ended Priority Queue)를 구현한다. 다음 명령을 처리한다.

• I N: 정수 N 삽입
• D 1: 최댓값 삭제
• D -1: 최솟값 삭제

모든 연산을 처리한 후 남은 원소의 최댓값과 최솟값을 출력한다. 비어 있으면 "EMPTY"를 출력한다.

입력

첫째 줄에 테스트 케이스 수 T가 주어진다.
각 테스트 케이스의 첫째 줄에 연산 수 k가 주어진다. (1 ≤ k ≤ 1,000,000)
다음 k개의 줄에 연산이 주어진다.

출력

각 테스트 케이스마다 최댓값과 최솟값을 공백으로 구분하여 출력하거나 "EMPTY"를 출력한다.

예제 입력 1

2
7
I 16
I -5643
D -1
D 1
D 1
I 123
D -1
2
I -45
I 653

예제 출력 1

EMPTY
653 -45