Рациональное приближение
Многочлен p(x) степени n может использоваться для аппроксимации функции f(x), если его коэффициенты совпадают с первыми n коэффициентами степенного ряда функции f(x) (разложенной около x = 0). Например,
К сожалению, многочлены не всегда хорошо подходят для аппроксимации функций с особенностями. Чтобы решить эту проблему, можно использовать рациональные функции вида p(x)/q(x), где p(x) и q(x) — многочлены. Вас попросили в Approximate Calculation Machinery решить эту задачу, чтобы они могли включить ваше решение в свое программное обеспечение для приближенных вычислений.
Даны m, n и первые m+n коэффициентов степенного ряда функции f(x). Необходимо вычислить два многочлена p(x) и q(x) степеней не более m-1 и n-1 соответственно, такие, что разложение в степенной ряд q(x)·f(x)-p(x) имеет 0 в качестве первых m+n-1 коэффициентов, и 1 в качестве коэффициента при члене x^{m+n-1}. Иными словами, нужно найти p(x) и q(x) такие, что
где ... содержит члены со степенями x выше, чем m+n-1. Таким образом, f(x) может быть аппроксимирована как p(x)/q(x).
Определения
Многочлен p(x) степени n может быть записан как p_0 + p_1x + p_2x^2 + ... + p_nx^n, где p_i — целые числа в этой задаче.
Разложение функции f(x) в степенной ряд около 0 может быть записано как f_0 +f_1x+f_2x^2+..., где f_i — целые числа в этой задаче.
Входные данные
Входные данные состоят из нескольких случаев. Каждый случай представлен одной строкой в формате m n f_0 f_1 ... f_{m+n-1}, где f_{i } — коэффициент при x_i в разложении функции f в степенной ряд. Вы можете предположить, что 1 ≤ m, 1 ≤ n ≤ 4, 2 ≤ m+n ≤ 10, и f_{i } — целые числа такие, что |f_i| ≤ 5. Конец ввода обозначается строкой m = n = 0, без коэффициентов для f. Вы можете предположить, что для данных входных данных существует единственное решение.
Выходные данные
Для каждого тестового случая выведите две строки. На первой строке напечатайте многочлен p(x), а на второй — q(x). Многочлен p(x) должен быть представлен как список пар (p_i, i), расположенных в порядке возрастания i, где p_i — ненулевой коэффициент для члена x_i. Каждый ненулевой коэффициент p_i должен быть напечатан как a/b, где b > 0 и a/b — дробь в наименьших терминах. Если b = 1, напечатайте только a. Если p(x) = 0, выведите строку (0, 0). Разделяйте пары в списке пробелом. Многочлен q(x) должен быть напечатан аналогично. Между случаями вставьте пустую строку.