Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Fractran
Time Limit: 5000MSMemory Limit: 30000K
Total Submissions: 479Accepted: 154

Description

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

Formally, we define a sequence by S0=N, and Sj+1=fiSj, if for 1<=i<=k, the number fiSj is an integer but the numbers f1Sj, ..., fi-1Sj are not.

For example, if we have the list of eight fractions f1=170/39, f2=19/13, f3=13/17, f4=69/95, f5=19/23, f6=1/19, f7=13/7, f8=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.

Input

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 f1, ..., fk. 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.

Output

For each test case output on a line m numbers e1, ..., em, separated by one space character, such that 2e1, ..., 2ek 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.

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

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator