Одночлен - это выражение, состоящее из однобуквенных переменных с операциями умножения и возведения в целочисленную степень. Именами переменных являются малые латинские буквы. Умножение обозначается символом '*' (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 1
a
b
|
a
b
|
|
2
|
1 1
x^8
x^9
|
1
x
|