This page is still under construction.

Parts of this page are still being built. What you see may change.

Peculiar Primes

Time limit1sMemory limit128 MB

Summary
List every integer in [X, Y] whose prime factors all belong to a given set of at most 10 primes, or print none.
Level

Medium5 of 10

Topics
Backtracking, Math, Number theory, Sorting
Solved
No attempts yet

Problem

Corruption has reached even the academic world. There are rumors that certain mathematicians have been pressured to favor some primes over others: they have stopped using a few "forbidden" primes entirely, and now build numbers only from a restricted set of allowed primes.

Reproduce such a restricted world. Given a set of allowed primes, a positive integer is constructible if it can be written as a product of powers of those primes and of no other prime. Equivalently, every prime factor of the number must belong to the given set.

For example, if the allowed primes are {2,3}\{2, 3\}, then 1,2,3,4,6,8,9,12,…1, 2, 3, 4, 6, 8, 9, 12, \dots are constructible, while 5,7,10,14,…5, 7, 10, 14, \dots are not.

Note that the number 11 needs no prime factors at all, so it is always constructible.

Input

The input consists of several scenarios.

Each scenario is given on three lines:

  • The first line contains a single integer NN (1≤N≤101 \le N \le 10), the number of allowed primes.
  • The second line contains NN primes 2≤P1<P2<⋯<PN<100002 \le P_1 < P_2 < \dots < P_N < 10000, separated by single spaces. All of them are guaranteed to be prime.
  • The third line contains two integers XX and YY (1≤X≤Y<2311 \le X \le Y < 2^{31}), separated by a single space.

The list of scenarios ends with a line containing a single zero, which must not be processed.

Output

For each scenario, print on its own line every integer in the closed interval [X,Y][X, Y] that is constructible from the given primes.

Print the qualifying numbers in strictly increasing order, without duplicates, separated by a single comma (,) and with no spaces. If no number in [X,Y][X, Y] is constructible, print the word none instead.

Examples3

  1. Example 1

    Input
    1
    3
    1 12
    2
    2 3
    10 20
    3
    2 3 5
    20 30
    1
    17
    20 30
    0
    
    Expected output
    1,3,9
    12,16,18
    20,24,25,27,30
    none
    
  2. Example 2

    Input
    1
    2
    1 100
    0
    
    Expected output
    1,2,4,8,16,32,64
    
  3. Example 3

    Input
    2
    2 5
    1 50
    0
    
    Expected output
    1,2,4,5,8,10,16,20,25,32,40,50