배달 기록의 체크섬 복구

문제

배달 앱의 보안 담당자는 전송 중 일부 내용이 달라졌을 수 있는 주문 기록을 점검하고 있다. 각 기록에는 주문 번호, 갱신 번호, 바이트열을 16진수로 인코딩한 문자열, 체크섬이 들어 있다. 같은 주문의 기록이 여러 번 도착할 수 있으며, 갱신 번호가 큰 기록이 더 나중에 작성된 내용을 뜻한다. 다만 입력에 나타난 순서는 작성 순서와 다를 수 있다. 인코딩 문자열은 두 글자씩 끊어 왼쪽부터 하나의 바이트로 해석한다. 각 글자는 0부터 9, A부터 F, a부터 f 중 하나이며, 영문자의 대소문자는 값에 영향을 주지 않는다. 예를 들어 문자열 0a10은 값이 각각 10과 16인 두 바이트를 뜻한다. 앞에 있는 0도 인코딩의 일부이므로 생략하거나 다른 바이트와 합쳐서는 안 된다. 복호화한 바이트열의 길이를 K, 왼쪽부터 각 바이트의 값을 x_1, x_2, …, x_K라고 하자. 이 기록에서 계산한 체크섬은 x_1+2x_2+…+Kx_K를 1009로 나눈 나머지다. 계산한 값이 기록에 적힌 체크섬과 같을 때만 그 기록을 유효하다고 판단한다. 이 문제에서는 이러한 일치 여부만으로 유효성을 결정한다. 각 주문에 대해 유효한 기록 중 갱신 번호가 가장 큰 기록 하나를 남긴다. 갱신 번호가 같은 유효한 기록이 여러 개라면 입력에서 먼저 나타난 기록을 남긴다. 유효하지 않은 기록은 갱신 번호가 아무리 커도 선택에 영향을 주지 않는다. 유효한 기록이 하나도 없는 주문은 결과에서 제외한다. 점검이 끝나면 남은 주문을 주문 번호가 작은 순서대로 출력한다. 선택된 인코딩 문자열은 모든 영문자를 대문자로 바꾸어 출력하되, 바이트의 순서와 앞자리 0은 그대로 유지한다. 남은 주문이 없으면 그 사실을 나타내는 개수만 출력한다.

입력

첫째 줄에 기록 수 N이 주어진다. 1≤N≤10,000이다.
다음 N개 줄에 주문 번호 I, 갱신 번호 V, 인코딩 문자열 H, 기록된 체크섬 C가 공백으로 주어진다. I,V,C는 정수이며 1≤I≤9,999, 0≤V≤999, 0≤C≤1,008이다.
H의 길이는 2 이상 24 이하인 짝수이며, 각 문자는 0~9, A~F, a~f 중 하나다. 따라서 각 기록은 1바이트 이상 12바이트 이하를 담는다. 정수는 불필요한 앞자리 0 없이 주어진다.

출력

첫째 줄에 선택된 주문 수를 출력한다. 이어서 각 주문에 대해 주문 번호, 선택된 갱신 번호, 대문자로 정규화한 인코딩 문자열을 공백으로 구분하여 한 줄씩 출력한다. 주문 번호의 오름차순으로 출력한다. 선택된 주문이 없다면 첫째 줄의 0만 출력한다.

6
12 2 0a10 42
3 1 ff 255
12 3 0102 6
12 2 aa 170
3 4 0001 2
8 0 00 1

2
3 4 0001
12 2 0A10

2
1 0 00 1
2 999 fF 254

0

3
7 5 000a 20
7 5 14 20
7 4 FF 255

1
7 5 000A

출처: Devin.KR 자체 제작