21935_Fractran

To play the "fraction game" corresponding to a given list f₁, f₂, ..., f_k of fractions and starting integer N, you repeatedly multiply the integer you have at any stage (initially N) by the earliest f_i in the list for which the answer is integral. Whenever there is no such f_i, the game stops.

Formally, we define a sequence by S₀=N, and S_j+1=f_i S_j, if for 1 ≤ i ≤ k, the number f_iS_j is an integer but the numbers f₁S_j, ..., f_i-1S_j are not.

For example, if we have the list of eight fractions f₁=170/39, f₂=19/13, f₃=13/17, f₄=69/95, f₅=19/23, f₆=1/19, f₇=13/7, f₈=1/3, and start with N=21, we produce the (finite) sequence ( 21, 39, 170, 130, 190, 138, 114, 6, 2 ). In general, the sequence may be infinite.

Given a fraction list and a starting integer calculate a part of the defined sequence. Actually, we are interested only in the powers of 2 that appear in the sequence.

The input contains several test cases. Every test case starts with three integers m, N, k. You may assume that 1 ≤ m ≤ 40, 1 ≤ N ≤ 1000, and 1 ≤ k ≤ 100. Then follow k fractions f₁, ..., f_k. For each fraction, first its numerator is given, followed by its denominator. You may assume that both are positive integers less than 1000 and their greatest common divisor is 1. The last test case is followed by a zero.

For each test case output on a line m numbers e₁, ..., e_m, separated by one space character, such that 2^e₁, ..., 2^e_k are the first m numbers in the defined sequence that are powers of 2. You may assume that there are at least m powers of 2 among the first 7654321 elements of the sequence.

1 21 8 170 39 19 13 13 17 69 95 19 23 1 19 13 7 1 3
20 2 14 17 91 78 85 19 51 23 38 29 33 77 29 95 23 77 19 1 17 11 13 13 11 15 2 1 7 55 1
0

1
1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67