Numbers with no forbidden prefixes P83364


Statement
 

pdf   zip

html

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
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++