이중 큐

신설된 발칸 투자 그룹 은행(BIG-Bank)이 부쿠레슈티에 새 지점을 열었다. 이 지점은 IBM 루마니아가 제공한 최신 전산 환경을 갖추고 최신 정보 기술을 사용한다. 여느 은행처럼 각 고객은 양의 정수 $K$로 식별되며, 서비스를 받으러 은행에 도착하면 양의 정수 우선순위 $P$를 받는다. 이 은행의 젊은 관리자들이 낸 발상 하나가 서비스 시스템의 소프트웨어 엔지니어를 놀라게 했다. 그들은 전통을 깨고, 때때로 우선순위가 가장 높은 고객 대신 가장 낮은 고객을 창구로 부르자고 제안한 것이다. 그리하여 시스템은 다음과 같은 종류의 요청을 받는다.

• 0: 시스템이 서비스를 중단해야 한다.
• 1 K P: 고객 $K$를 우선순위 $P$로 대기 목록에 추가한다.
• 2: 우선순위가 가장 높은 고객을 서비스하고 대기 목록에서 제거한다.
• 3: 우선순위가 가장 낮은 고객을 서비스하고 대기 목록에서 제거한다.

당신이 할 일은 요청된 서비스 정책을 구현하는 프로그램을 작성하여 은행의 소프트웨어 엔지니어를 돕는 것이다.

입력의 각 줄에는 가능한 요청 중 하나가 주어지며, 마지막 줄에만 중단 요청(코드 0)이 있다. 새 고객을 목록에 추가하는 요청(코드 1)이 들어올 때, 목록에는 같은 식별자를 가진 고객이나 같은 우선순위를 가진 고객이 이미 존재하지 않는다고 가정해도 된다. 식별자 $K$는 항상 $10^6$보다 작고, 우선순위 $P$는 항상 $10^7$보다 작다. 한 고객은 여러 번 서비스를 받으러 올 수 있으며, 그때마다 서로 다른 우선순위를 받을 수 있다.

코드 2 또는 3인 각 요청에 대해, 서비스한 고객의 식별자를 표준 출력의 별도의 줄에 출력한다. 그러한 요청이 들어왔을 때 대기 목록이 비어 있다면 $0$을 출력한다.