쇼핑몰 알림 패킷 수신기

문제

온라인 쇼핑몰의 주문 알림 장치는 작은 수신기로 네 종류의 알림을 보낸다. 임베디드 담당자는 수신기가 저장한 패킷 기록을 분석하여 실제로 접수한 알림 수를 계산하려 한다. 기록에는 통신 상태를 확인하기 위한 패킷과 재전송된 패킷도 함께 들어 있다. 각 패킷은 정확히 1바이트이며, 두 자리의 대문자 16진수 문자열로 기록되어 있다. 예를 들어 0A는 십진수 10을 나타낸다. 한 바이트의 비트 위치를 가장 낮은 자리부터 0번, 1번, …, 7번으로 부른다. 7번 비트는 유효 표시이다. 이 비트가 0인 패킷은 내용에 관계없이 무시한다. 6번과 5번 비트가 이루는 두 자리 이진수는 알림 통로 번호이며, 번호는 0부터 3까지이다. 나머지 4번부터 0번까지의 다섯 비트가 이루는 이진수는 순서 번호이며, 값은 0부터 31까지이다. 수신기는 통로마다 가장 최근에 접수한 순서 번호를 하나씩 기억한다. 처음에는 어느 통로에도 기억한 번호가 없다. 유효 표시가 1인 패킷을 읽었을 때, 해당 통로에 기억한 번호가 없거나 기억한 번호가 이번 순서 번호와 다르면 알림을 한 건 접수한다. 접수한 뒤에는 그 통로의 기억한 번호를 이번 순서 번호로 바꾼다. 기억한 번호와 같으면 재전송으로 판단하여 무시한다. 다른 통로의 패킷을 처리해도 현재 통로의 기억은 바뀌지 않는다. 유효 표시가 0인 패킷도 어떤 통로의 기억도 바꾸지 않는다. 순서 번호의 크기나 증가 방향은 판단에 사용하지 않으며, 과거에 접수했던 번호라도 가장 최근 번호와 다르면 다시 접수한다. 기록을 입력 순서대로 처리한 뒤 통로별 접수 건수와 가장 많이 접수한 통로를 구한다.

입력

첫째 줄에 패킷 수인 정수 N이 주어진다. 1≤N≤100,000이다.
둘째 줄에 패킷 N개가 공백으로 구분되어 주어진다. 각 패킷은 0부터 9와 A부터 F만으로 이루어진 정확히 두 자리 문자열이며, 00부터 FF까지의 값을 나타낸다.

출력

첫째 줄에 통로 0, 1, 2, 3의 접수 건수를 순서대로 공백으로 구분하여 출력한다. 둘째 줄에 접수 건수가 가장 많은 통로 번호를 출력한다. 동점이면 번호가 가장 작은 통로를 출력한다. 모든 접수 건수가 0이면 둘째 줄에 -1을 출력한다.

9
80 80 01 A1 81 A1 C0 E0 80

3 1 1 1
0

4
00 7F 20 41

0 0 0 0
-1

5
A0 E1 A0 E2 A1

0 2 0 2
1

출처: Devin.KR 자체 제작