Fractran

To play the "fraction game" for a given list of fractions $f_1, f_2, \dots, f_k$ and a starting integer $N$, repeatedly multiply the integer you currently hold (initially $N$) by the earliest $f_i$ in the list for which the product is an integer. As soon as no such $f_i$ exists, the game stops.

Formally, define the sequence by $S_0 = N$ and $S_{j+1} = f_i S_j$, where $i$ is the smallest index with $1 \le i \le k$ such that $f_i S_j$ is an integer while $f_1 S_j, \dots, f_{i-1} S_j$ are not.

For example, with the eight fractions $f_1 = 170/39$, $f_2 = 19/13$, $f_3 = 13/17$, $f_4 = 69/95$, $f_5 = 19/23$, $f_6 = 1/19$, $f_7 = 13/7$, $f_8 = 1/3$ and $N = 21$, the game produces 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, we are interested only in the powers of $2$ that appear in the sequence.

The input contains several test cases. Each test case begins with three integers $m$, $N$, and $k$, where $1 \le m \le 40$, $1 \le N \le 1000$, and $1 \le k \le 100$. Then follow the $k$ fractions $f_1, \dots, f_k$: for each fraction the numerator is given first, then the denominator. Both are positive integers less than $1000$ whose greatest common divisor is $1$. The last test case is followed by a single $0$.

For each test case, output on one line the $m$ numbers $e_1, \dots, e_m$, separated by single spaces, such that $2^{e_1}, \dots, 2^{e_m}$ are the first $m$ powers of $2$ that occur in the sequence. You may assume that at least $m$ powers of $2$ occur among the first $7654321$ elements of the sequence.