Rational Approximation

A polynomial $p(x)$ of degree $n$ can be used to approximate a function $f(x)$ by setting the coefficients of $p(x)$ to match the leading coefficients of the power series of $f(x)$ (expanded about $x = 0$). For example,

$\frac{1}{1-x} \approx 1 + x + x^2 + \cdots + x^n.$

Unfortunately, polynomials are "nice" and do not work well when approximating functions that behave poorly (for example, functions with singularities). To overcome this, we can instead approximate $f(x)$ by a rational function of the form $p(x)/q(x)$, where $p(x)$ and $q(x)$ are polynomials.

Given $m$, $n$, and the first $m+n$ coefficients of the power series of $f(x)$, compute two polynomials $p(x)$ and $q(x)$ of degrees at most $m-1$ and $n-1$, respectively, such that the power series expansion of $q(x)f(x) - p(x)$ has $0$ as its first $m+n-1$ coefficients and $1$ as the coefficient of the $x^{m+n-1}$ term. In other words, find $p(x)$ and $q(x)$ such that

$q(x)\cdot f(x) - p(x) = x^{m+n-1} + \cdots,$

where $\cdots$ contains terms with powers of $x$ higher than $m+n-1$. From this, $f(x)$ can be approximated by $p(x)/q(x)$.

The input consists of multiple cases. Each case is given on one line in the form

m n f0 f1 ... f(m+n-1)

where $f_i$ is the coefficient of $x^i$ in the power series expansion of $f$. You may assume that $1 \le m$, $1 \le n \le 4$, $2 \le m+n \le 10$, and that each $f_i$ is an integer with $|f_i| \le 5$. The end of input is indicated by a line containing $m = n = 0$ with no coefficients for $f$. You may assume that the solution for each input is unique.

For each test case, print two lines. Print the polynomial $p(x)$ on the first line and $q(x)$ on the second line.

Print the polynomial $p(x)$ as a list of pairs $(p_i, i)$ arranged in ascending order of $i$, where $p_i$ is a non-zero coefficient of the $x^i$ term. Print each non-zero coefficient $p_i$ as $a/b$, where $b > 0$ and $a/b$ is in lowest terms; if $b = 1$, print only $a$ (omit $b$). If $p(x) = 0$, print a line containing only $(0,0)$. Separate the pairs in the list by a single space.

Print the polynomial $q(x)$ in the same manner. Insert a blank line between cases.

A polynomial $p(x)$ can be written as $p_0 + p_1 x + p_2 x^2 + \cdots$, and likewise for $q(x)$. In this problem the coefficients $p_i$ and $q_i$ are rational numbers.

The power series expansion of $f(x)$ about $0$ can be written as $f_0 + f_1 x + f_2 x^2 + \cdots$, where the $f_i$ are integers in this problem.