Continued Fraction
Continued Fraction
The (simple) continued fraction representation of a real number r is an expression obtained by an iterative process of representing r as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal, and so on. In other words, a continued fraction representation of r is of the form
where a0
, a1
, a2
, ... are integers and a1
, a2
, ... > 0. We call the ai
-values partial quotients. For example, in the continued fraction representation of 5.4, the partial quotients are a0
= 5, a1
= 2, a2
= 2. This representation of a real number has several applications in theory and practice. If r is a rational number, the partial quotients are eventually all zero, so we only need to consider a finite number of partial quotients.
Given two rational numbers in continued fraction representation, your task is to perform the four elementary arithmetic operations on these numbers and display the results in continued fraction representation.
Input
Consists of three lines. The first line contains two integers n1
and n2
, where 1 ≤ ni
≤ 9 is the number of partial quotients of rational number ri
for 1 ≤ i ≤ 2. The second line contains the partial quotients of r1
and the third line contains the partial quotients of r2
. The absolute values of the quotients are not more than 10 and you may assume that r1
> r2
> 0.
Output
Display the partial quotients of the continued fraction representations of r1
+ r2
, r1
- r2
, r1
* r2
and r1
/ r2
, in order, each in a line. Consecutive partial quotients on each line are separated by a single space. Do not print any trailing zero partial quotients.
4 3 5 1 1 2 5 2 2
11 0 5 30 4 6 1 27