노노그램 QR

간단한 퍼즐은 머리를 식히기에 좋습니다.

노노그램은 각 행과 열에 연속된 검은 칸의 개수가 순서대로 주어질 때, 이 단서로 그림을 완성하는 퍼즐입니다. 아래 그림을 참고하세요.

그림 1: 완성되지 않은 노노그램.

그림 2: 완성된 노노그램.

우리가 노노그램으로 그릴 그림은 QR 코드입니다. 노트에 있는 그림 3은 다음 형태의 QR 코드 2,000개를 담고 있습니다.

• QR 코드를 해독하면 숫자열이 나옵니다. 이 숫자열을 9로 구분하면 총 2n개의 숫자열이 다시 나옵니다. 각 숫자열은 n by n 노노그램의 행과 열에 주어진 단서를 인코딩한 것입니다. 단서는 행은 위에서 아래로, 그다음 열은 왼쪽에서 오른쪽으로 순서대로 주어집니다. 각 숫자열의 인코딩 규칙은 다음과 같습니다.

  • 단서 0은 빈 숫자열로 인코딩됩니다.

  • 그 외의 경우, 단서에 있는 하나 이상의 수는 다음 형식으로 인코딩됩니다.

    • 주어진 수 x가 8 이하이면 x-1을 적습니다.
    • 주어진 수 x가 8보다 크면 8과 x-9를 순서대로 적습니다.

  • 수들 사이에 별도의 구분자는 없으며, 단서의 수는 항상 16 이하입니다.

• 주어진 노노그램을 풀면 QR 코드가 나옵니다. 이 QR 코드를 해독하면 각 QR 코드의 데이터가 나옵니다.

각 QR 코드가 담은 데이터는 다음 두 종류 중 하나입니다.

• 지시자 데이터. 항상 네 자리의 수입니다. 네 숫자를 xxyy라고 할 때, xx는 행 번호, yy는 열 번호에 해당하는 QR 코드를 가리킵니다. 이 QR 코드를 (xx, yy)로 표기합니다. 예를 들어 (0, 0)은 가장 왼쪽 위에 있는 QR 코드이고, (0, 1)은 그 오른쪽에 있는 QR 코드입니다. 행 번호와 열 번호는 0부터 시작합니다. 지시자 데이터를 만나면 해당하는 QR 코드로 이동해 해독을 계속합니다.
• 플래그. 지시자 데이터 형식에 속하지 않으면 모두 플래그입니다. 이 문자열을 찾아 제출해야 합니다.

시작 위치의 QR 코드에서 출발해 플래그를 찾아내세요.

이때 플래그를 찾는 동안 등장한 모든 지시자 데이터의 곱을 469,762,049로 나눈 나머지도 함께 출력합니다. 이 값을 checkprod라고 부릅니다.

예를 들어 (1, 1)에서 시작해 (2, 2), (3, 3)을 따라 플래그를 찾았다면, checkprod는 0202 * 0303 = 61,206을 469,762,049로 나눈 나머지인 61,206입니다. (1, 1)은 지시자 데이터로 알아낸 값이 아니라 처음에 주어진 값이므로 곱에 포함하지 않습니다.

서브태스크 번호가 입력됩니다.

첫째 줄에 플래그를 출력합니다.

둘째 줄에 checkprod를 출력합니다.

그림 3: QR 코드의 목록.