Finite automaton

Today Vasya learned what a deterministic finite automaton (DFA) is, and he is eager to tell everyone about it.

A DFA has $N$ states. At any moment during its work, the automaton is in exactly one of these states. Its input is an arbitrary string. After the work ends, the automaton reports whether the string is acceptable.

The automaton works as follows:

1. At the start, the automaton is in the start state, which is always marked as such.
2. It reads all symbols of the string from left to right. After reading each symbol, it can switch to a different state, as described below.
3. After the whole string is read, the automaton decides the answer from the state it ended in.

For each state $u$ and each possible symbol $c$, the automaton defines the state it moves to after reading $c$ while in state $u$. That new state can be $u$ itself or another state. Each state also has a fixed answer (accepted or not) for the case where the automaton finishes there.

Vasya took the first seminar on the subject, built all sorts of DFAs, and received the following homework. Build a DFA that, given a non-negative integer written in base $B$, accepts those and only those integers divisible by the given modulus $M$.

To keep things simple, Vasya assumes that the input number:

• starts with its most significant digit (written on the left, big-endian);
• can have leading zeroes;
• can be empty. An empty input is zero and is always divisible by $M$.

Vasya is a born perfectionist. He wants to learn how to build DFAs that meet the requirements with the smallest possible number of states. He asked you to help him.

The only line of the input contains two integers: $B$, the base of the positional numeral system in which the input number is written, and $M$, the modulus that all accepted numbers must be divisible by and all rejected numbers must not be divisible by ($2 \le B \le 16$, $2 \le M \le 10^5$).

Print the description of the smallest DFA that meets the requirements.

The first line contains two integers: $N$, the number of states ($N \ge 2$), and $S$, the start state number ($0 \le S < N$). States are numbered consecutively from 0.

The second line contains $N$ space-separated symbols. The $k$-th symbol is the answer the automaton gives when it ends in state $k$ ($0 \le k < N$). The symbol is 'G' if the string is accepted and 'B' otherwise.

The next $N$ lines each contain $B$ integers. The $k$-th number on the $i$-th of these lines is the state the automaton ends up in after reading digit $k$ while in state $i$ ($0 \le i < N$, $0 \le k < B$). Each number can be any integer from 0 to $N-1$.

Shown below is the DFA used in the sample. The letter 'S' and a number are shown near each state. The bold arrow points to the start state. Each normal arrow shows the state the DFA moves to after reading the digit written near it.