Символьная математика
На протяжении многих лет программные системы, способные выполнять символьные вычисления, значительно улучшились. Популярные коммерческие системы в настоящее время включают Mathematica и Maple; система Sage также доступна бесплатно.
В этой задаче вам предстоит реализовать небольшую часть такой системы: возможность вычислять (символически) f(g(x)) для функций f(x) и g(x), выраженных в виде многочленов с членами, имеющими неотрицательные целые показатели степени и целые коэффициенты.
Входные данные
Многочлены будут представлены во входных и выходных данных как последовательность членов, за которой сразу следует конец строки. Каждый член состоит из знака плюс или минус (кроме первого члена, у которого нет знака, если он положительный), целого коэффициента (опускается, если он равен 1 и показатель степени члена не равен нулю), строчной буквы 'x', циркумфлекса ('^'), и неотрицательного показателя степени. Если показатель степени равен 1, то циркумфлекс и показатель степени опускаются. Если показатель степени равен 0, то 'x' также опускается. Члены даны в порядке убывания их показателей степени, и каждый член должен иметь уникальный показатель степени. Таблица ниже показывает несколько примеров многочленов в этой форме вместе с их традиционным алгебраическим представлением.
Входные данные будут содержать пары строк. Первая строка каждой пары дает многочлен f(x), а вторая строка каждой пары дает многочлен g(x). Строка после последней пары многочленов будет содержать только символ конца строки. Пробелы и табуляции никогда не будут появляться во входных данных.
Коэффициенты и показатели степени во входных и выходных многочленах никогда не будут превышать 1000000 по абсолютной величине.
Выходные данные
Для каждой пары входных строк отобразите номер входного случая (1, 2, …), входные многочлены и многочлен, представляющий значение f(g(x)). Соответствующим образом обозначьте многочлены. Отобразите пустую строку после вывода для каждого случая. Следуйте формату, показанному в примерах ниже.