Задача B. Сокращение одночленов

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Одночлен — это выражение, состоящее из однобуквенных переменных с операциями умножения и возведения в целочисленную степень. Именами переменных являются малые латинские буквы. Умножение обозначается символом '*' (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, разделённые пробелами. Следующие N + M строк содержат по одному одночлену каждая.

Формат выходного файла

В выходном файле должны быть две строки, содержащие соответственно числитель и знаменатель результата. Если после сокращения в числителе и/или в знаменателе не остаётся ни одной переменной, вместо одночлена следует вывести число 1.

Ограничения

3 ≤ N, M ≤ 999. Длина каждой строки не превосходит 100 символов.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1
x*x^7*x
x*y*z
y^2*z
x^10
y

0.070s 0.012s 15