Звичайний многочлен
Вчитель математики пан Мацудайра навчає своїх учнів розкладу та факторизації многочленів. Минулого тижня він доручив учням написати два многочлени (з однією змінною x) і знайти НСД (найбільший спільний дільник) цих многочленів як домашнє завдання, але йому стало нудно перевіряти їхні відповіді вручну. Тому вас просять написати програму для перевірки відповідей.
Розглядаються лише ті многочлени з цілими коефіцієнтами, які називаються цілими многочленами.
Коли дано два цілі многочлени A і B, цілий многочлен C є спільним дільником A і B, якщо існують деякі цілі многочлени X і Y такі, що A = CX і B = CY.
НСД двох цілих многочленів є спільним дільником, який має найвищий степінь (для x, тут); вам потрібно написати програму, яка обчислює НСД двох многочленів.
Відомо, що НСД двох даних многочленів є унікальним, якщо ігнорувати множник-константу. Тобто, коли C і D є обидва НСД деяких двох многочленів A і B, p×C = q×D для деяких ненульових цілих чисел p і q.
Вхідні дані
Вхід складається з кількох наборів даних. Кожен набір даних складається з пари рядків введення, кожен з яких представляє многочлен як вираз, визначений нижче.
Первинний елемент — це змінна x, послідовність цифр 0–9 або вираз, укладений у дужки (...). Приклади: x, 99, (x+1).
Фактор — це первинний елемент сам по собі або первинний елемент, за яким слідує показник степеня. Показник степеня складається з символу ^, за яким слідує послідовність цифр 0–9. Приклади: x^05, 1^15, (x+1)^3.
Член складається з одного або кількох прилеглих факторів. Приклади: 4x, (x+1)(x-2), 3(x+1)^2.
Вираз — це один або кілька членів, з'єднаних або +, або -. Крім того, перший член виразу може бути опціонально переданий зі знаком мінус -. Приклади: -x+1, 3(x+1)^2-x(x-1)^2.
Цілі константи, показники степеня, множення (прилеглі), додавання (+) та віднімання/негування (-) мають свої звичайні значення. Послідовність цифр завжди інтерпретується як ціла константа. Наприклад, 99 означає 99, а не 9×9.
Будь-які підвирази введення, коли повністю розгорнуті та нормалізовані, мають коефіцієнти менші за 100 і степені x менші за 10. Послідовності цифр у показниках степеня представляють ненульові значення.
Усі набори даних розроблені так, щоб стандартний алгоритм з 32-бітними цілими числами з двійковим доповненням міг вирішити проблему без переповнень.
Кінець введення позначається рядком, що містить крапку.
Вихідні дані
Для кожного набору даних виведіть вираз многочлена НСД в одному рядку у форматі нижче.
c_0x^p_0 ± c_1x^p_1...± c_nx^p_n
Де c_i і p_i (i = 0, ..., n) є додатними цілими числами з p_0 > p_1 > ... > p_n, і найбільший спільний дільник {c_i | i = 0, ..., n} є 1.
Додатково:
Коли c_i дорівнює 1, його слід опустити, якщо відповідний p_i не дорівнює 0,
x^0 слід опустити повністю, і
x^1 слід записати як x.