유한 오토마타

바샤는 오늘 결정적 유한 오토마타(DFA)가 무엇인지 배웠고, 이를 모두에게 말하고 싶어 안달이 났다.

DFA에는 $N$개의 상태가 있다. 오토마타는 작업 중 어느 순간에든 이 상태들 중 정확히 하나에 있다. 입력은 임의의 문자열이다. 작업이 끝나면 오토마타는 그 문자열을 받아들일지 여부를 알려 준다.

오토마타는 다음과 같이 동작한다.

1. 작업을 시작할 때 오토마타는 항상 표시된 시작 상태에 있다.
2. 문자열의 모든 기호를 왼쪽에서 오른쪽으로 하나씩 읽는다. 기호를 읽은 뒤 아래에서 설명하는 대로 다른 상태로 옮겨 갈 수 있다.
3. 문자열을 끝까지 읽으면 마지막으로 머문 상태를 보고 답을 정한다.

오토마타의 각 상태 $u$와 가능한 각 기호 $c$에 대해, 상태 $u$에 있을 때 $c$를 읽은 뒤 옮겨 갈 상태가 정해져 있다. 그 새 상태는 $u$ 자신일 수도 있고 다른 상태일 수도 있다. 각 상태에는 작업이 그 상태에서 끝났을 때의 답(받아들임 또는 거부)도 정해져 있다.

바샤는 첫 세미나에서 여러 종류의 DFA를 만들었고, 다음 숙제를 받았다. $B$진법으로 적힌 음이 아닌 정수가 주어졌을 때, 주어진 모듈러스 $M$으로 나누어떨어지는 정수만 받아들이고 그 밖의 정수는 받아들이지 않는 DFA를 만들어라.

문제를 단순하게 하기 위해 바샤는 입력 수가 다음과 같다고 가정한다.

• 가장 높은 자리의 숫자부터 시작한다(왼쪽에 쓰는 빅엔디안 방식이다).
• 앞에 0이 올 수 있다.
• 빈 입력일 수 있다. 이때 수는 0이며 $M$으로 확실히 나누어떨어진다.

바샤는 타고난 완벽주의자라서, 조건을 만족하는 DFA 중 상태 수가 가장 적은 것을 만드는 방법을 배우고 싶어 한다. 그는 이를 도와 달라고 부탁했다.

입력은 한 줄이며 두 정수를 담는다. $B$는 입력 수를 표현하는 위치 기수법의 기수이고, $M$은 받아들여야 하는 수가 모두 나누어떨어지고 받아들이지 않아야 하는 수가 나누어떨어지지 않는 모듈러스다($2 \le B \le 16$, $2 \le M \le 10^5$).

요구 조건을 만족하는 가장 작은 DFA의 기술을 출력한다.

첫 줄에는 두 정수를 출력한다. $N$은 상태 수($N \ge 2$)이고, $S$는 시작 상태의 번호($0 \le S < N$)다. 상태는 0부터 순서대로 번호가 붙는다.

둘째 줄에는 $N$개의 기호를 공백으로 구분해 출력한다. $k$번째 기호는 작업이 상태 $k$에서 끝났을 때 오토마타가 내는 답이다($0 \le k < N$). 문자열을 받아들이면 'G', 그렇지 않으면 'B'를 쓴다.

이어서 $N$줄을 출력하며, 각 줄에는 $B$개의 정수가 있다. $i$번째 줄의 $k$번째 수는 상태 $i$에 있던 오토마타가 숫자 $k$를 읽은 뒤 도달하는 상태 번호다($0 \le i < N$, $0 \le k < B$). 각 수는 0부터 $N-1$ 사이의 어떤 정수든 될 수 있다.

아래 그림은 예제에 쓰인 DFA다. 각 상태 옆에는 'S'와 번호가 적혀 있다. 굵은 화살표는 시작 상태를 가리킨다. 일반 화살표는 화살표 옆에 적힌 숫자를 읽은 뒤 DFA가 옮겨 가는 상태를 나타낸다.