Continued Fractions#1023

Continued Fractions

1 second

128 megabytes

Very easy

Let $b_{0}$ b_0, $b_{1}$ b_1, $b_{2}$ b_2, $\dots$ , $b_{n}$ b_n be integers such that $b_{k} > 0$ b_k > 0 for $k > 0$ k > 0. The continued fraction of order $n$ with coefficients $b_{1}$ b_1, $b_{2}$ b_2, $\dots$ , $b_{n}$ b_n and initial term $b_{0}$ b_0 is defined by the following expression:

b_{0} + \frac{1}{b _{1} + \frac{1}{b _{2} + \frac{1}{⋱ + \frac{1}{b _{n}}}}}

b_0 + \cfrac{1}{b_1 + \cfrac{1}{b_2 + \cfrac{1}{\ddots + \cfrac{1}{b_n}}}}

This expression can be abbreviated as $[b_{0}; b_{1}, \dots, b_{n}]$ [b_0; b_1, \ldots, b_n].

For example, a continued fraction of order $n = 3$ n=3 with $[2; 3, 1, 4]$ [2;3,1,4] is equivalent to:

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

2 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{4}}}

Write a program that finds the continued fraction expansion for a given rational number. To ensure uniqueness, $b_{n} > 1$ b_n > 1.

Input

The input consists of an undetermined number of rational numbers. Each rational number is given as a fraction: numerator and denominator.

Output

For each rational number, output its continued fraction representation on a separate line.

Examples

Example 1

Loading

b_{0}

b_{1}

b_{2}

b_{n}

b_{k} > 0

k > 0

b_{1}

b_{2}

b_{n}

b_{0}

b_{0} + \frac{1}{b _{1} + \frac{1}{b _{2} + \frac{1}{⋱ + \frac{1}{b _{n}}}}}

[b_{0}; b_{1}, \dots, b_{n}]

n = 3

[2; 3, 1, 4]

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

b_{n} > 1