It is easy to obtain (6x2-5x-5)/(x3-2x2-x+2) from 1/(x+1) + 2/(x-1) + 3/(x-2). But how about the other way around?
Given a rational function in the form
where bn is 1. The simple partial fraction decomposition is given by
for some constants Ai and ri (i=1, 2, ..., n). Assume that the denominator has n integer roots. Your job is to compute the partial fraction of R(x).
Input
The input consists of several test cases. For each case, the first line contains a positive integer n which is the degree of the polynomial in the denominator of R(x). The following two lines contain integers { a0, a1, ..., an-1 } and { b0, b1, ..., bn-1 } respectively.
Output
For each test case, first output in a line { r1, r2, ..., rn } in non-decreasing order. Then if there is a partial fraction, output in the next line { A1, A2, ..., An }; otherwise print "No simple partial fraction".
It is guaranteed that the denominator of R(x) has only integer roots. Ai's must be accurate up to 2 decimal places. All the numbers must be separated by exactly one space, and no extra space is allowed at the end of the lines.
The output of two consecutive cases must be separated by a blank line. No extra line is allowed at the end of the outputs.
Sample Input:
3
-5 -5 6
2 -1 -2
3
-5 -3 5
2 -1 -2
2
-1 1
1 2
Sample Output:
-1 1 2
1.00 2.00 3.00
-1 1 2
0.50 1.50 3.00
-1 -1
No simple partial fraction
