Fractran

주어진 분수 목록 $f_1, f_2, \dots, f_k$ 와 시작 정수 $N$ 에 대한 "분수 게임"은 다음과 같이 진행한다. 현재 가지고 있는 정수(처음에는 $N$)에, 곱한 결과가 정수가 되는 목록 중 가장 앞선 $f_i$ 를 곱한다. 그런 $f_i$ 가 하나도 없으면 게임을 멈춘다.

엄밀하게, 수열을 $S_0 = N$ 으로 정의하고 $S_{j+1} = f_i S_j$ 로 정의한다. 여기서 $i$ 는 $1 \le i \le k$ 범위에서 $f_i S_j$ 는 정수이면서 $f_1 S_j, \dots, f_{i-1} S_j$ 는 모두 정수가 아닌 가장 작은 첨자이다.

예를 들어 여덟 개의 분수 $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$ 과 $N = 21$ 로 시작하면 유한 수열 $(21, 39, 170, 130, 190, 138, 114, 6, 2)$ 가 만들어진다. 일반적으로 이 수열은 무한할 수도 있다.

분수 목록과 시작 정수가 주어질 때, 우리는 이 수열에 나타나는 $2$ 의 거듭제곱에만 관심이 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 정수 $m$, $N$, $k$ 로 시작하며 $1 \le m \le 40$, $1 \le N \le 1000$, $1 \le k \le 100$ 을 만족한다. 그 뒤에 $k$ 개의 분수 $f_1, \dots, f_k$ 가 이어지며, 각 분수는 분자를 먼저, 분모를 나중에 준다. 분자와 분모는 모두 $1000$ 보다 작은 양의 정수이고 서로소이다(최대공약수가 $1$). 마지막 테스트 케이스 뒤에는 $0$ 하나가 온다.

각 테스트 케이스마다 한 줄에 $m$ 개의 수 $e_1, \dots, e_m$ 을 공백 하나로 구분하여 출력한다. 이때 $2^{e_1}, \dots, 2^{e_m}$ 은 수열에 나타나는 $2$ 의 거듭제곱 중 처음 $m$ 개이다. 수열의 처음 $7654321$ 개 원소 안에 $2$ 의 거듭제곱이 적어도 $m$ 개 존재한다고 가정해도 된다.