예약 식별자 검증 대장

문제

가상의 병원에서 보안 담당자는 외부 예약 단말이 보낸 예약 식별자 기록을 검증한다. 단말은 식별자를 그대로 보내지 않고 각 문자의 바이트 값을 두 자리 16진수로 바꾸어 이어 붙인다. 병원에서 사용하는 예약 식별자는 숫자 문자 여섯 개로 이루어진 문자열이다. 맨 앞의 0도 식별자의 일부이므로 지우면 안 된다. 예를 들어 식별자 000042와 000420은 서로 다른 식별자다. 각 기록에는 인코딩 문자열 H와 체크섬 C가 들어 있다. H는 항상 대문자 16진수 문자 열두 개로 이루어진다. H를 왼쪽부터 두 문자씩 나누고 각 조각을 16진수 정수로 해석하면 여섯 바이트 b₁, b₂, …, b₆을 얻는다. 여기서 사용하는 문자 코드는 ASCII이며, 숫자 문자 0부터 9까지의 바이트 값은 각각 48부터 57까지다. 인코딩 문자열의 형식이 올바르더라도 복원한 바이트가 숫자 문자를 나타내지 않을 수 있다. 기록의 검사값은 b₁ + 2b₂ + 3b₃ + 4b₄ + 5b₅ + 6b₆을 97로 나눈 나머지다. 여섯 바이트가 모두 48 이상 57 이하이고, 검사값이 기록에 적힌 C와 같을 때만 그 기록을 유효하다고 판단한다. 두 조건 중 하나라도 만족하지 못하면 해당 기록을 버린다. 체크섬이 맞는다는 이유만으로 숫자가 아닌 문자를 허용해서는 안 된다. 같은 예약이 여러 번 전송되어 동일한 식별자를 가진 기록이 반복될 수 있다. 유효한 기록이 하나라도 있는 식별자는 검증 대장에 정확히 한 번만 올린다. 같은 식별자를 복원하는 다른 기록이 유효하지 않더라도 이미 확인된 유효한 기록을 취소하지 않는다. 입력 순서와 전송 횟수는 대장의 순서에 영향을 주지 않는다. 모든 기록을 검사한 뒤 검증 대장에 올라간 서로 다른 식별자의 수와 식별자 목록을 출력하는 프로그램을 작성한다. 목록은 여섯 자리 문자열의 사전순으로 정렬한다. 모든 식별자의 길이가 같고 숫자로만 이루어지므로 이 순서는 수의 크기순과도 같다. 다만 출력할 때에는 반드시 앞의 0을 포함한 여섯 자리 형태를 유지한다.

입력

첫째 줄에 기록 수 N이 주어진다. N은 1 이상 10,000 이하의 정수다.
다음 N개 줄에는 인코딩 문자열 H와 정수 C가 공백 하나로 구분되어 주어진다. H의 길이는 정확히 12이며 각 문자는 0부터 9 또는 A부터 F 중 하나다. C는 0 이상 96 이하의 정수다. 같은 기록이 여러 번 주어질 수 있다.

출력

첫째 줄에 검증 대장에 올라간 서로 다른 식별자의 수 K를 출력한다. 이후 K개 줄에 식별자를 사전순으로 하나씩 출력한다. 각 식별자는 앞의 0을 포함하여 정확히 여섯 자리로 출력한다. K가 0이면 첫째 줄에 0만 출력한다.

6
303030313233 70
303030303037 80
303030313233 70
303030303432 71
393939393939 33
303030303041 43

3
000007
000123
999999

3
303030303030 39
303030303041 43
FFFFFFFFFFFF 20

0

4
303030303432 70
303030303030 38
303030303432 0
303030303030 38

2
000000
000042

출처: Devin.KR 자체 제작