Theory: A DFA for divisibility

Build, rather than read, a DFA: one state for each remainder.

What to build

A program that builds the remainder DFA for m and uses it to decide which binary words are divisible by m.

Requirements

  • Print states m first.
  • Then, for each word, print accept if its value is divisible by m, else reject, by running the DFA, not by converting the whole word.

Input

Line 1: m. Line 2: n. Then n binary words (a word may be an empty line).

Output

states m, then n lines.

Constraints

1 ≤ m ≤ 9; words have at most 60 bits.

Example

Input:

3
4
110
111
1001
0

Output:

states 3
accept
reject
accept
accept

Why it works

Appending a bit doubles the value and adds the bit, so only the remainder needs to be remembered: m states suffice.

Examples

Example 1 · Input
3
4
110
111
1001
0
Expected output
states 3
accept
reject
accept
accept
Example 2 · Input
2
3
10
11
0
Expected output
states 2
accept
reject
accept

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Use the remainder as the state: reading bit b turns remainder r into (2r + b) mod m.

Hint 2

The empty word has value 0, which every m divides.

Solution

Show one correct solution (try it yourself first)
m = int(input())
delta = {(r, bit): (2 * r + int(bit)) % m for r in range(m) for bit in "01"}
print("states", m)
for _ in range(int(input())):
    state = 0
    for bit in input():
        state = delta[(state, bit)]
    print("accept" if state == 0 else "reject")

Lesson: Designing DFAs: memory, complement and product →