Умножение в диэдральной группе
Диэдральная группа представляет собой множество 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 - корректный ответ.