Раціональне наближення
Поліном p(x) степеня n може бути використаний для апроксимації функції f(x), підбираючи коефіцієнти p(x) так, щоб вони відповідали першим n коефіцієнтам степеневого ряду функції f(x) (розкладеної навколо x = 0). Наприклад,
На жаль, поліноми не завжди добре підходять для апроксимації функцій, які мають особливості. Щоб вирішити цю проблему, можна використовувати раціональні функції виду p(x)/q(x), де p(x) і q(x) є поліномами. Вас попросила Машина Апроксимаційних Обчислень вирішити цю задачу, щоб вони могли інтегрувати ваше рішення у своє програмне забезпечення для апроксимаційних обчислень.
Дано 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 (і опустіть b). Якщо p(x) = 0, виведіть рядок, що містить лише (0, 0). Розділіть пари у списку одним пробілом. Поліном q(x) слід вивести таким же чином. Вставте порожній рядок між випадками.