번호표 단말기 패킷 해석

문제

은행 창구의 번호표 단말기는 32비트 부호 없는 정수 하나를 패킷 하나로 서버에 보낸다. 패킷은 최상위 비트를 31번, 최하위 비트를 0번이라 할 때 다음과 같이 해석한다. 31~29번 비트는 종류 T(0~7), 28~25번 비트는 등급 C(0~15, 작을수록 급한 손님), 24~9번 비트는 번호표 번호 ID(0~65535), 8~1번 비트는 창구 번호 K(0~255), 0번 비트는 패리티 비트다. 패킷 전체 32비트 중 1인 비트의 개수가 홀수이면 손상된 패킷이므로 아무 효과 없이 무시한다. 손상되지 않은 패킷은 T에 따라 처리하며, 그 종류에서 쓰지 않는 필드의 값은 무시한다. T=1은 발급이다. 등급 C, 번호 ID인 손님을 대기열에 넣는다. 이미 한 번이라도 발급 처리된 ID라면(호출되었거나 취소된 번호도 포함) 중복 발급이므로 무시한다. T=2는 호출이다. 대기 중인 손님 중 C가 가장 작은 손님을, C가 같으면 먼저 발급된 손님을 대기열에서 꺼내 창구 K로 보낸다. T=3은 취소다. 번호 ID인 손님이 대기 중이면 대기열에서 뺀다. 대기 중이 아니면 아무 일도 일어나지 않으며 이 경우는 무시한 패킷으로 세지 않는다. T가 0, 4, 5, 6, 7이면 알 수 없는 종류이므로 무시한다. 패킷을 입력된 순서대로 처리하라. 호출 패킷마다 어느 손님이 어느 창구로 갔는지 한 줄씩 출력하고, 마지막에 무시한 패킷의 수를 출력한다. 무시한 패킷은 손상된 패킷, 알 수 없는 종류의 손상되지 않은 패킷, 중복 발급 패킷이다. 한 패킷이 여러 이유에 해당해도 한 번만 센다.

입력

첫 줄에 패킷의 수 N(1 ≤ N ≤ 200000)이 주어진다. 이어서 N개의 줄에 패킷이 하나씩 주어진다. 각 패킷은 앞의 0을 포함한 소문자 16진수 8자리다.

출력

손상되지 않은 호출 패킷을 처리할 때마다 한 줄에 'K ID'를 출력한다. 호출 시점에 대기 중인 손님이 없으면 'K EMPTY'를 출력한다. 마지막 줄에 무시한 패킷의 수를 출력한다.

8
24000a00
22000e01
40000007
60000a00
40000008
40000006
00000000
22000e01

3 7
4 EMPTY
3

3
26001401
26001201
400001ff

255 10
0

3
ffffffff
40000001
24000a00

0 EMPTY
1

출처: Devin.KR 자체 제작