Numbers with no forbidden prefixes P83364

Statement

thehtml

Write a backtracking program to print all the n-digit numbers such that none of its prefixes (the whole number included) is a multiple of any of m given forbidden divisors d1, …, dm.

For instance, if n = 3, m = 6 and the forbidden divisors are 2, 3, 5, 7, 11 and 19, then 137 is allowed, because none of its three prefixes 1, 13 and 137 is a multiple of any di. By contrast, 433 is not allowed, because some of its three prefixes 4, 43 and 433 is multiple os some di (4 ‍is multiple of 2).

Input

Input consists of several cases. Each case begins with n and m, followed by m different integer numbers between 2 and 1000. You can assume 1 ≤ n ≤ 9 and 1 ≤ m ≤ 15.

Output

For every case, print all the numbers with exactly n digits and no forbidden prefixes, one per line and in increasing order. Print a line with 10 dashes at the end of each case.

Public test cases
• Input

```3 6
2 3 5 7 11 19
1 1
2
2 6
3 4 7 11 12 13
2 9
2 3 5 7 9 11 13 17 19
9 10
199 191 193 17 13 11 7 5 3 2
```

Output

```131
137
139
173
179
----------
1
3
5
7
9
----------
10
17
19
23
25
29
50
53
58
59
----------
----------
197399999
197933933
197933993
197933999
----------
```
• Information
Author