Continued Fractions

Continued Fractions

Let b0, b1, b2, ..., bn be integers with bk > 0 for k > 0. The continued fraction of order n with coeficients b1, b2, ..., bn and the initial term b0 is defined by the following expression


which can be abbreviated as [b0; b1, ..., bn].

An example of a continued fraction of order n = 3 is [2;3,1,4]. This is equivalent to


Write a program that determines the expansion of a given rational number as a continued fraction. To ensure uniqueness, make bn > 1.


Consists of an undetermined number of rational numbers. Each rational number is defined by two integers, numerator and denominator.


For each rational number output the corresponding continued fraction on a separate line.

Time limit 1 second
Memory limit 128 MiB
Input example #1
43 19
1 2
Output example #1