Задача №400. Сокращение одночленов
Одночлен - это выражение, состоящее из однобуквенных переменных с операциями умножения и возведения в целочисленную степень. Именами переменных являются малые латинские буквы. Умножение обозначается символом '*' (ASCII 42), возведение в степень - символом '^' (ASCII 94). Показатель степени состоит из одной десятичной цифры от 1 до 9. Примеры одночленов: t, a*b*c^2, y*d^1*y^9.
Требуется по данным N + M одночленам построить дробь, равную произведению первых N одночленов, делённому на произведение оставшихся M одночленов. При этом:
1) Числитель и знаменатель дроби должны быть одночленами.
2) Переменная не должна встречаться в дроби более одного раза (т. е. дробь необходимо сократить).
3) Степени переменных должны быть целыми числами большими или равными 2.
4) В числителе и знаменателе переменные должны быть отсортированы по алфавиту.
В первой строке входного файла содержатся числа N и M (1 <= N, M <= 999), разделённые пробелами.
Следующие N + M строк содержат по одному одночлену каждая. Длина каждой строки не превосходит 100 символов.
В выходном файле должны быть две строки, содержащие соответственно числитель и знаменатель результата. Если после сокращения в числителе и/или в знаменателе не остаётся ни одной переменной, вместо одночлена следует вывести число 1.
1 1 a b
a b
1 1 x^8 x^9
1 x