재생 조각의 검증 기록

문제

음악 스트리밍 서비스의 보안 담당자는 재생 조각을 전달하는 중계 장치의 수신 기록을 점검한다. 각 기록에는 곡 번호, 조각의 내용을 인코딩한 문자열, 전송 장치가 계산한 검증값이 들어 있다. 담당자는 기록의 내용으로 검증값을 다시 계산하여 두 값이 일치하는 기록만 집계하려 한다. 조각의 내용은 정확히 4바이트이며, 입력에서는 길이가 8인 16진수 문자열로 주어진다. 문자열을 왼쪽부터 두 글자씩 나누면 차례대로 첫 번째부터 네 번째 바이트가 된다. 각 바이트의 값은 0 이상 255 이하이다. 숫자 0부터 9와 알파벳 A부터 F 또는 a부터 f를 사용하며, 같은 알파벳의 대문자와 소문자는 같은 값을 나타낸다. 예를 들어 00000100은 순서대로 0, 0, 1, 0인 네 바이트를 나타낸다. 검증에는 다음과 같은 간단한 해시 계산을 사용한다. 처음에 정수 h를 0으로 둔다. 네 바이트를 왼쪽부터 하나씩 읽으며, 읽은 바이트의 값을 b라고 할 때 h를 (17 × h + b)를 251로 나눈 나머지로 바꾼다. 네 바이트를 모두 처리한 뒤의 h가 해당 내용의 검증값이다. 계산한 값이 기록에 적힌 검증값과 같으면 그 기록은 정상 기록이다. 다르면 그 기록은 집계에서 제외한다. 정상 기록 수가 가장 많은 곡을 찾아야 한다. 정상 기록 수가 같은 곡이 여러 개라면 곡 번호가 가장 작은 곡을 선택한다. 같은 곡 번호와 같은 내용이 여러 번 등장하더라도 각 줄은 별개의 수신 기록이므로 정상 여부를 각각 판정하여 센다. 정상 기록이 하나도 없는 곡은 선택 대상이 아니다. 전체 입력에 정상 기록이 하나도 없다면 선택할 곡이 없다고 보고한다.

입력

첫째 줄에 기록의 수 N이 주어진다. N은 1 이상 20,000 이하의 정수이다.
다음 N개 줄에는 곡 번호 S, 인코딩된 문자열 X, 기록에 적힌 검증값 C가 공백으로 구분되어 주어진다. S는 1 이상 9,999 이하의 정수이다. X는 0~9, A~F, a~f만으로 이루어진 길이 8의 문자열이다. C는 0 이상 250 이하의 정수이다. 기록은 임의의 순서로 주어진다.

출력

정상 기록이 하나 이상 있으면 선택한 곡 번호와 그 곡의 정상 기록 수를 공백으로 구분하여 한 줄에 출력한다. 정상 기록이 하나도 없으면 -1만 출력한다.

7
20 00000001 1
8 00000100 17
20 00010000 38
8 00000000 0
3 00000001 0
20 01000000 145
8 00000002 2

8 3

4
9 00000000 0
2 00000001 1
9 00000001 2
2 00000100 18

2 1

3
1 00000000 1
4 00000001 0
4 00000100 16

-1

출처: Devin.KR 자체 제작