## FRACTAN - Fractan

`f`_{1}, f_{2}, ..., 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`

, and _{0}=N`S`

, if for _{j+1}=f_{i}S_{j}`1<=i<=k`

, the number `f`

is an integer but the numbers _{i}S_{j}`f`

are not.
_{1}S_{j}, ..., f_{i-1}S_{j}

For example, if we have the list of 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`

, and start with _{8}=1/3`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.

### Input Specification

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`

.
For each fraction, first its numerator is given, followed by its denominator.
You may assume that both are positive integers less than _{1}, ..., f_{k}`1000`

and their greatest common divisor is `1`

.
The last test case is followed by a zero.

### Output Specification

For each test case output on a line `m`

numbers `e`

, separated by one space character, such that _{1}, ..., e_{m}`2`

are the first ^{e1}, ..., 2^{ek}`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.

### Sample Input

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

### Sample Output

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

hide comments

.::Manish Kumar::.:
2010-06-26 13:55:03
as u can see till now there is no python submission accepted , plz increase time limit for python programmers. |

Added by: | Wanderley GuimarÄƒes |

Date: | 2007-09-19 |

Time limit: | 0.303s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO |

Resource: | University of Ulm Local Contest 2004 |