UPC 바코드 읽기

FoodVictory의 물류 관리자인 영우는 바코드 데이터베이스 일부를 잃어버렸다. 이 사실이 알려지면 큰 문제가 되므로, 영우는 손상된 바코드 이미지와 일치할 수 있는 올바른 UPC-A 코드를 모두 찾아야 한다.

UPC-A 바코드는 12자리 십진수를 나타낸다. 바코드는 밝은 막대와 어두운 막대가 번갈아 나타나는 95개의 비트로 표현되며, 전체 구조는 SLLLLLLMRRRRRRE이다.

• S는 시작 패턴 101이다.
• M은 가운데 패턴 01010이다.
• E는 끝 패턴 101이다.
• 각 L 패턴은 앞쪽 6자리 십진수에 대응한다.
• 각 R 패턴은 뒤쪽 6자리 십진수에 대응한다.

비트 1은 어두운 막대, 비트 0은 밝은 막대를 뜻한다. 각 숫자 패턴은 7개의 비트로 이루어져 있으므로, 코드 비트의 총 길이는 3 + 6*7 + 5 + 6*7 + 3 = 95이다. 실제 바코드의 양끝에는 최소 9개의 밝은 막대가 있지만, 입력에는 95개의 코드 비트만 주어진다.

마지막 십진수 자리는 체크 숫자이다. digitN을 십진수의 N번째 자리, check_digit을 마지막 자리라고 할 때 체크 숫자는 다음과 같이 계산한다.

CheckSum = 3*(digit1 + digit3 + digit5 + digit7 + digit9 + digit11) + digit2 + digit4 + digit6 + digit8 + digit10;
Code = CheckSum % 10;
If (Code == 0) check_digit = 0;
else check_digit = (10 - Code);

바코드 스캐너는 카메라로 좁은 바코드 이미지를 읽고, 그 이미지에서 95개의 코드 비트를 추론한다. 바코드가 뒤집힌 상태로 읽히면 비트열이 반대 방향으로 읽힌다. 또한 색 대비가 낮거나 반사가 있으면 어떤 비트가 0인지 1인지 알 수 없을 수 있다.

손상된 바코드는 0, 1, ?로 이루어진 길이 95의 문자열로 주어진다. ?는 해당 비트가 손상되어 알 수 없음을 뜻한다. 주어진 문자열과 일치할 수 있는 모든 올바른 UPC-A 코드를 출력하라. 비트열이 반대 방향으로 읽힌 경우도 함께 고려해야 한다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 바코드 비트열의 앞 50자가, 둘째 줄에는 나머지 45자가 주어진다.

각 테스트 케이스마다 먼저 입력과 일치하는 올바른 바코드의 개수를 출력한다. 일치하는 바코드가 8개보다 많으면 실제 개수 대신 9를 출력한다.

그 다음 줄부터 일치하는 바코드를 증가하는 순서로 한 줄에 하나씩 출력한다. 일치하는 바코드가 9개 이상이면 처음 8개만 출력한다.