시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB394867122.684%

문제

The (simple) continued fraction representation of a real number r is an expression obtained by an iterative process of representing r as a 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

\[r = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}\]

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, and a2 = 2. This representation of a real number has several applications in theory and practice.

While irrational numbers like √2 require an infinite set of partial quotients, any rational number can be written as a continued fraction with a unique, finite set of partial quotients (where the last partial quotient is never 1 in order to preserve uniqueness). Given two rational numbers in continued fraction representation, your task is to perform the four elementary arithmetic operations on these numbers and display the result in continued fraction representation.

입력

Each test case consists of three lines. The first line contains two integers n1 and n2, 1 ≤ ni ≤ 9 specifying the number of partial quotients of two rational numbers r1 and r2. The second line contains the partial quotients of r1 and the third line contains the partial quotients of r2. The partial quotients satisfy |a0| ≤ 10 and 0 < ai ≤ 10, the last partial quotient will never be 1, and r2 is non-zero. A line containing two 0’s will terminate input.

출력

For each test case, display the case number followed by the continued fraction representation of r1+r2, r1−r2, r1×r2, and r1/r2 in order, each on a separate line. Use 64-bit integers for all of your calculations (long long in C++ and long in Java).

예제 입력 1

4 3
5 1 1 2
5 2 2
0 0

예제 출력 1

Case 1:
11
0 5
30 4 6
1 27

예제 입력 2

4 3
5 1 1 2
5 2 2
4 3
5 1 1 2
5 2 2
0 0

예제 출력 2

Case 1:
11
0 5
30 4 6
1 27
Case 2:
11
0 5
30 4 6
1 27