같은 조각의 다른 내용

문제

음악 스트리밍 서비스의 보안 담당자는 전송 기록에서 내용이 서로 다른 음악 조각을 찾으려 한다. 하나의 음악 조각에는 정수 식별자가 붙는다. 재전송 때문에 같은 식별자가 여러 기록에 나타날 수 있지만, 정상적으로 관리된 조각이라면 그 내용은 항상 같아야 한다. 각 기록에는 조각 식별자, 내용을 16진수로 인코딩한 문자열, 전송자가 적은 체크섬이 들어 있다. 문자열은 왼쪽부터 두 글자씩 나누어 바이트로 해석한다. 각 바이트는 0 이상 255 이하의 정수다. 16진수의 영문자는 대문자와 소문자를 구별하지 않는다. 예를 들어 문자열 0aFF와 0Aff는 모두 두 바이트 10, 255를 나타낸다. 바이트의 순서와 개수는 내용의 일부이므로, 문자열 00과 0000은 서로 다른 내용을 나타낸다. 내용이 왼쪽부터 b₁, b₂, …, bₖ라면 계산한 체크섬은 (1×b₁ + 2×b₂ + … + k×bₖ)를 251로 나눈 나머지다. 계산한 체크섬이 기록에 적힌 체크섬과 같은 기록만 검사를 통과한다. 통과하지 못한 기록은 이후 판단에서 완전히 제외한다. 검사를 통과한 기록 중 같은 식별자에 서로 다른 내용이 두 종류 이상 있으면 그 식별자를 충돌 식별자로 부른다. 같은 내용이 여러 번 기록된 것만으로는 충돌이 아니다. 또한 서로 다른 내용의 체크섬이 우연히 같을 수 있으므로, 체크섬이 같다는 이유만으로 내용을 같다고 판단해서는 안 된다. 검사를 통과한 기록이 하나도 없는 식별자도 충돌 식별자가 아니다. 모든 기록을 조사하여 충돌 식별자의 개수와 목록을 구하는 프로그램을 작성한다. 목록은 식별자의 수치가 작은 순서로 출력하며, 같은 식별자는 한 번만 출력한다.

입력

첫째 줄에 기록 수 N이 주어진다. N은 1 이상 10,000 이하의 정수다.
다음 N개 줄에 조각 식별자 I, 16진수 문자열 H, 기록된 체크섬 C가 공백으로 구분되어 주어진다. I는 1 이상 100,000 이하의 정수이고, C는 0 이상 250 이하의 정수다. H의 길이는 2 이상 16 이하의 짝수이며, 각 글자는 0부터 9까지의 숫자 또는 a부터 f까지의 소문자 또는 A부터 F까지의 대문자다. 각 기록은 1개 이상 8개 이하의 바이트를 나타낸다. 기록은 임의의 순서로 주어진다.

출력

첫째 줄에 충돌 식별자의 개수 K를 출력한다. 다음 K개 줄에 충돌 식별자를 오름차순으로 하나씩 출력한다. 충돌 식별자가 없으면 첫째 줄에 0만 출력한다.

7
10 0201 4
3 00 0
10 0002 4
8 FF 4
3 0000 0
8 ff 4
10 0300 4

2
3
10

5
7 AA 170
7 aa 170
7 AB 170
9 0001 2
9 0001 2

0

출처: Devin.KR 자체 제작