회의실 출입 패킷 집계

문제

회의실 관리 장치의 네트워크 담당자는 출입 센서가 보낸 패킷을 해석하여 각 회의실의 현재 인원을 계산하려 한다. 관리 대상 회의실에는 1번부터 R번까지 번호가 붙어 있으며, 기록을 처리하기 전에는 모든 회의실의 인원이 0명이다. 패킷은 수신된 순서대로 처리한다. 각 패킷은 정확히 16비트이며, 입력에서는 네 자리의 16진수 문자열로 주어진다. 가장 오른쪽 비트를 0번 비트라고 할 때, 15번과 14번 비트는 종류, 13번부터 8번까지의 여섯 비트는 회의실 코드, 7번부터 0번까지의 여덟 비트는 인원 값을 나타낸다. 각 필드는 부호 없는 정수로 해석한다. 회의실 코드가 c이면 이 패킷이 가리키는 회의실 번호는 c+1이다. 종류가 이진수 01이면 입실 기록이다. 해당 회의실의 인원에 패킷의 인원 값을 더한다. 종류가 이진수 10이면 퇴실 기록이다. 해당 회의실의 인원에서 패킷의 인원 값을 빼되, 결과가 음수가 되면 그 회의실의 인원을 0명으로 바꾼다. 예를 들어 현재 인원이 2명인 회의실에서 5명의 퇴실 기록을 받으면 처리 후 인원은 0명이다. 인원 값이 0인 입실 또는 퇴실 기록도 허용되며, 현재 인원을 바꾸지 않는다. 종류가 이진수 00이면 상태 확인 패킷이고, 이진수 11이면 진단 패킷이다. 이 두 종류는 회의실 코드와 인원 값에 관계없이 무시한다. 또한 패킷이 가리키는 회의실 번호가 R보다 크면 종류에 관계없이 무시한다. 무시한 패킷은 어떤 회의실의 인원에도 영향을 주지 않는다. 모든 패킷을 처리한 뒤 인원이 가장 많은 회의실의 번호와 그 인원을 출력한다. 최대 인원이 같은 회의실이 여러 개이면 번호가 가장 작은 회의실을 선택한다. 단, 모든 회의실의 인원이 0명이면 선택할 회의실이 없는 것으로 보고 0 0을 출력한다.

입력

첫째 줄에 회의실 수 R과 패킷 수 N이 공백으로 구분되어 주어진다. R과 N은 정수이며 1≤R≤64, 1≤N≤60,000이다.
다음 N개의 줄에 패킷이 수신된 순서대로 하나씩 주어진다. 각 패킷은 문자 0~9와 대문자 A~F로만 이루어진 길이 4의 16진수 문자열이다. 앞자리의 0도 생략하지 않는다. 패킷의 정수 값은 0 이상 65,535 이하이다.

출력

선택한 회의실 번호와 모든 패킷을 처리한 뒤의 해당 회의실 인원을 공백으로 구분하여 한 줄에 출력한다. 모든 회의실의 인원이 0명이면 0 0을 출력한다.

3 8
4005
4103
8002
4204
8201
C1FF
4309
0000

1 3

2 6
8007
4102
8105
C009
4208
000A

0 0

출처: Devin.KR 자체 제작