이집트 분수

고대 이집트인은 분수를 표현하는 독특한 방법을 사용했다. 분자가 $1$인 분수, 즉 단위분수 $\frac{1}{k}$ 를 나타내는 상형문자를 만들고, 이 단위분수들을 더해서 다른 분수를 나타냈다. 이 방식으로는 분자가 $1$보다 큰 분수를 직접 쓸 수 없었기 때문에, 언제나 단위분수의 합으로 분수를 표현했다.

예를 들어 $\frac{3}{4}$ 는 다음과 같이 나타낼 수 있다.

$\frac{3}{4} = \frac{1}{2} + \frac{1}{4}$

하나의 분수를 나타내는 방법은 여러 가지일 수 있다. 예컨대 $\frac{3}{4}$ 는 다음처럼 쓸 수도 있다.

$\frac{3}{4} = \frac{1}{4} + \frac{1}{4} + \frac{1}{4}$

분수 $\frac{M}{N}$ 이 주어졌을 때, 이 분수를 그리디(greedy) 방법으로 단위분수의 합으로 나타내려고 한다. 그리디 방법이란, 현재 남은 분수에서 뺄 수 있는 가장 큰 단위분수를 골라 빼는 과정을 남은 분수가 $0$ 이 될 때까지 반복하는 방법이다. 예를 들어 $\frac{9}{20}$ 에 그리디 방법을 적용하면 다음과 같다.

$\frac{9}{20} = \frac{1}{3} + \frac{1}{9} + \frac{1}{180}$

다만 단위분수의 분모가 지나치게 커지는 것을 막기 위해 다음 제한을 둔다. 단위분수를 하나 뺀 뒤에 남는 분수(기약분수)의 분모는 항상 $1{,}000{,}000$ 보다 작아야 한다. 만약 뺄 수 있는 가장 큰 단위분수를 뺐을 때 남는 분모가 $1{,}000{,}000$ 이상이 된다면 그 단위분수는 사용할 수 없다. 이때는 분모를 $1$ 씩 키운 그다음 단위분수( $\frac{1}{d}$ 대신 $\frac{1}{d+1}$ )를 차례로 시도하여, 남는 분모가 $1{,}000{,}000$ 보다 작아지는 가장 큰 단위분수를 사용한다.

예를 들어 $\frac{17}{69}$ 에서 시작하면 처음 두 단위분수는 $\frac{1}{5}$ 와 $\frac{1}{22}$ 가 되고 $\frac{7}{7590}$ 이 남는다. 이 상태에서 뺄 수 있는 가장 큰 단위분수는 $\frac{1}{1085}$ 이지만,

$\frac{7}{7590} - \frac{1}{1085} = \frac{1}{1647030}$

처럼 남는 분모가 $1{,}000{,}000$ 을 넘는다. 따라서 $\frac{1}{1085}$ 는 쓸 수 없고, 그다음 단위분수인 $\frac{1}{1086}$ 을 빼면

$\frac{7}{7590} - \frac{1}{1086} = \frac{1}{686895}$

가 되어 조건을 만족한다. 결국 정답은 다음과 같다.

$\frac{17}{69} = \frac{1}{5} + \frac{1}{22} + \frac{1}{1086} + \frac{1}{686895}$

모든 분수는 분모가 모두 같은 단위분수의 합으로도 나타낼 수 있다. 예를 들어 $\frac{M}{N}$ 은 $\frac{1}{N}$ 을 $M$ 번 더한 것과 같다. 따라서 이 방법으로 표현하지 못하는 분수는 없다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 두 정수 $M$ 과 $N$ 이 공백으로 구분되어 주어지며 분수 $\frac{M}{N}$ 을 뜻한다. $1 < M < N < 100$ 이고, $M$ 과 $N$ 의 최대공약수는 항상 $1$ 이다. 입력의 마지막 줄에는 0 0 이 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다, 위에서 설명한 그리디 방법으로 얻은 단위분수들의 분모 $D_1, D_2, D_3, \dots$ 를 한 줄에 공백으로 구분하여 출력한다. 즉

$\frac{M}{N} = \frac{1}{D_1} + \frac{1}{D_2} + \frac{1}{D_3} + \cdots$

를 만족하도록 하며, $D_1 \le D_2 \le D_3 \le \cdots$ 의 순서로 출력한다.