Диэдральная группа представляет собой множество D с мультипликативной операцией *, определенной на D. Множество D генерируется двумя элементами a и b. Операция умножения * явно записываться не будет, то есть a*a будет обозначаться как aa или a^2. Аналогично a*a*b будет записано как a^2b^1 или просто a^2b.
Диэдральная группа D имеет два целочисленных параметра m и n, где m ≥ 2 и n ≥ 2, таким образом диэдральную группу можно записать в виде D_{m,n}. Отношения, определяющие D_{m,n}, следующие:
a^m = a^0 = 1, b^n = b^0 = 1 и ba = a^{(m-1)}b.
Группа D_{m,n} содержит (mn) элементов, а именно
D_{m,n} = { a^jb^k | 0 ≤ j < m, 0 ≤ k < n } = { a^0b^0, a^1b^0, a^2b^0, ..., a^{(m-1)}b^0, ..., a^{(m-1)}b^{(n-1)} }.
Например, пусть m = 7 и n = 2. Элементы D_{7,2} имеют вид
{ a^0b^0, a^1b^0, a^2b^0, a^3b^0, a^4b^0, a^5b^0, a^6b^0, a^0b^1, a^1b^1, a^2b^1, a^3b^1, a^4b^1, a^5b^1, a^6b^1 }.
Умножение не коммутативно, то есть ba ≠ ab. На самом деле ba = a^6b согласно отношениям, определяющим D_{7,2}. Также a^ja^k = a^{(j+k)%m} и b^jb^k = b^{(j+k)%n}. Таким образом
(a^jb^k)(a^pb^q) ≠ (a^{(j+p)%m}b^{(k+q)%n}).
Чтобы правильно умножить два числа (a^3b^1) и (a^2b^1) из D_{7,2}, поступим следующим образом:
(a^3b^1)(a^2b^1) = (a^3b^0)(ba)(a^1b^1) = (a^3b^0)(a^6b^1)(a^1b^1),
так как ba = a^6b.
Поскольку a^3b^0a^6 = a^3a^6 = a^{(3+6)%7} = a^2, то можно найти произведение первых двух множителей, получив (a^3b^0)(a^6b^1) = (a^2b^1).
Таким образом
(a^3b^0)(a^6b^1)(a^1b^1) = (a^2b^1)(a^1b^1).
Перепишем выражение в виде
(a^2b^1)(a^1b^1) = (a^2b^0)(ba)(a^0b^1) = (a^2b^0)(a^6b^1)(a^0b^1) = (a^8b^2) = (a^1b^0).
Результатом произведения двух элементов (a^3b^1) и (a^2b^1) будет (a^3b^1)(a^2b^1) = (a^1b^0).
Вам следует написать программу, которая по заданным m, n и любым двум элементам (a^jb^k) и (a^pb^q) из диэдральной группы D_{m,n} корректно вычислит их произведение.
Входные данные состоят из нескольких тестов. Каждый тест располагается на нескольких строках. Первая строка каждого теста содержит problemID, m, n и p, разделенных пробелом. Значения m и n не превосходят 1000. Число p указывает на количество примеров на умножение в текущем тесте. Далее следует p строк, каждая из которых содержит два элемента из D_{m,n}, которые следует перемножить. Каждый элемент будет задан в виде a3b1 вместо a^3b^1. Данные для следующего теста идут сразу за предыдущим. Если problemID равно "ZZ", то это означает конец входных данных.
Для каждого примера на умножение следует вывести одну строку вида
ProblemID id: ajbk * apbq = arbs
где id - номер заданной на входе problemID, ajbk и apbq - элементы, которые следует перемножить, а arbs - корректный ответ.