유리 함수 근사

함수 $f(x)$는 차수가 $n$인 다항식 $p(x)$로 근사할 수 있다. $p(x)$의 계수를 $f(x)$의 멱급수 전개($x = 0$ 근방)의 앞쪽 계수와 일치시키면 된다. 예를 들어,

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

이다.

그러나 다항식은 '얌전한' 함수여서, 특이점을 가진 함수처럼 나쁘게 행동하는 함수를 근사할 때는 잘 맞지 않는다. 이를 해결하기 위해 두 다항식 $p(x)$, $q(x)$의 비 $p(x)/q(x)$ 형태의 유리 함수로 근사할 수 있다.

$m$, $n$과 $f(x)$ 멱급수의 처음 $m+n$개 계수가 주어진다. 차수가 각각 최대 $m-1$, $n-1$인 두 다항식 $p(x)$, $q(x)$를 구하라. 단, $q(x)f(x) - p(x)$의 멱급수 전개에서 처음 $m+n-1$개 계수가 모두 $0$이고 $x^{m+n-1}$ 항의 계수가 $1$이어야 한다. 즉,

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

를 만족해야 한다. 여기서 $\cdots$는 차수가 $m+n-1$보다 높은 항들을 뜻한다. 이렇게 하면 $f(x)$를 $p(x)/q(x)$로 근사할 수 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 한 줄에 다음 형식으로 주어진다.

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

여기서 $f_i$는 $f(x)$의 멱급수 전개에서 $x^i$의 계수이다. $1 \le m$, $1 \le n \le 4$, $2 \le m+n \le 10$이며, 모든 $f_i$는 $|f_i| \le 5$인 정수이다. 입력의 끝은 $m = n = 0$인 줄로 표시되고, 이 줄에는 $f$의 계수가 없다. 주어지는 입력에 대한 해는 유일하다고 가정해도 된다.

각 테스트 케이스마다 두 줄을 출력한다. 첫째 줄에 다항식 $p(x)$를, 둘째 줄에 $q(x)$를 출력한다.

다항식 $p(x)$는 $i$의 오름차순으로 정렬된 쌍 $(p_i, i)$의 목록으로 출력한다. 여기서 $p_i$는 $x^i$ 항의 $0$이 아닌 계수이다. $0$이 아닌 각 계수 $p_i$는 $a/b$ 꼴로 출력하되 $b > 0$이고 $a/b$는 기약분수여야 한다. 또한 $b = 1$이면 $a$만 출력한다($b$는 생략). $p(x) = 0$이면 $(0,0)$만 있는 줄을 출력한다. 목록의 쌍들은 공백 하나로 구분한다.

다항식 $q(x)$도 같은 방식으로 출력한다. 케이스와 케이스 사이에는 빈 줄을 하나 넣는다.

다항식 $p(x)$는 $p_0 + p_1 x + p_2 x^2 + \cdots$의 형태로 쓸 수 있으며, $q(x)$도 마찬가지이다. 이 문제에서 두 다항식의 계수 $p_i$, $q_i$는 유리수이다.

$f(x)$의 $x = 0$에 대한 멱급수 전개는 $f_0 + f_1 x + f_2 x^2 + \cdots$로 쓸 수 있으며, 이 문제에서 $f_i$는 정수이다.