예약 수신기의 마지막 장부

문제

한 병원에서는 진료 예약 단말기가 보낸 패킷을 작은 수신기에 모아 예약 장부를 관리한다. 수신기는 패킷을 받은 순서대로 처리하며, 모든 패킷을 처리한 뒤 예약자가 가장 많은 진료과를 안내 화면에 표시한다. 처음에는 어느 환자에게도 예약이 없다. 패킷 하나는 0 이상 65535 이하인 정수이며, 정확히 16개의 비트로 해석한다. 가장 오른쪽 비트의 번호를 0이라 한다. 비트 0부터 9까지는 환자 번호 p를 나타내며, p는 0 이상 1023 이하이다. 비트 10부터 12까지는 진료과 코드 d를 나타내며, d는 0 이상 7 이하이다. 안내 화면에 사용하는 진료과 번호는 d+1이다. 비트 13은 요청 종류 a를 나타낸다. a가 1이면 예약 등록 요청이고, 0이면 예약 취소 요청이다. 비트 14부터 15까지는 검사값 c를 나타내며, c는 0 이상 3 이하이다. 각 구간에서는 오른쪽 비트가 가장 낮은 자릿값을 갖는다. 수신기는 p, d, a를 비트 단위 배타적 논리합한 결과의 하위 2비트를 올바른 검사값으로 사용한다. 즉, c가 ((p XOR d XOR a) AND 3)과 같을 때만 패킷이 유효하다. XOR는 같은 위치의 두 비트가 다르면 1이 되는 연산이고, AND는 같은 위치의 두 비트가 모두 1일 때만 1이 되는 연산이다. 검사값이 다른 패킷은 장부에 아무 영향도 주지 않는다. 각 환자는 동시에 하나의 진료과에만 예약할 수 있다. 유효한 등록 요청을 받으면 해당 환자의 기존 예약을 없애고 요청에 적힌 진료과로 예약한다. 이미 같은 진료과에 예약되어 있다면 그대로 유지한다. 유효한 취소 요청은 해당 환자가 요청에 적힌 진료과에 예약되어 있을 때만 그 예약을 없앤다. 예약이 없거나 다른 진료과에 예약되어 있다면 아무 일도 일어나지 않는다. 모든 패킷을 처리한 뒤 예약자가 가장 많은 진료과 번호와 그 예약자 수를 구한다. 최대 예약자 수가 같은 진료과가 여러 개라면 번호가 가장 작은 진료과를 선택한다. 예약자가 한 명도 없다면 두 값 모두 0으로 정한다.

입력

첫째 줄에 패킷 수 N이 주어진다. N은 1 이상 60000 이하인 정수이다.
다음 N개의 줄에는 수신한 순서대로 패킷을 나타내는 정수 x가 하나씩 주어진다. x는 0 이상 65535 이하이다. 검사값이 올바르다는 보장은 없다.

출력

선택한 진료과 번호와 그 진료과의 최종 예약자 수를 공백으로 구분하여 한 줄에 출력한다. 최종 예약자가 한 명도 없다면 0 0을 출력한다.

6
8193
41986
25601
32770
1025
8192

2 1

2
24576
25601

1 1

2
24576
0

0 0

출처: Devin.KR 자체 제작