Dihedral Group Product

A dihedral group is a set $D$ with a multiplication $*$ defined on it. Every element of $D$ is built from two elements $a$ and $b$. The multiplication sign is almost never written out: the factors are written next to each other or collapsed into exponents. So $a*a$ is written $aa$ or $a^2$, and $a*a*b$ is written $a^2b^1$ or $a^2b$.

A dihedral group $D$ takes two parameters $m$ and $n$ with $m \ge 2$ and $n \ge 2$, and is written $D_{m,n}$. Three relations hold in $D_{m,n}$.

$a^m = a^0 = 1, \quad b^n = b^0 = 1, \quad ba = a^{m-1}b$

$D_{m,n}$ therefore has exactly $mn$ elements.

$D_{m,n} = \{a^jb^k \mid 0 \le j < m,\ 0 \le k < n\} = \{a^0b^0, a^1b^0, \dots, a^{m-1}b^0, \dots, a^{m-1}b^{n-1}\}$

For $m = 7$ and $n = 2$, $D_{7,2}$ consists of these 14 elements.

$\{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\}$

The multiplication is not commutative, so $ba \ne ab$. In $D_{7,2}$ the third relation reads $ba = a^6b$. Powers of a single letter combine as $a^ja^k = a^{(j+k) \bmod m}$ and $b^jb^k = b^{(j+k) \bmod n}$, but once the two letters mix you cannot simply add the exponents.

$(a^jb^k)(a^pb^q) \ne a^{(j+p) \bmod m}b^{(k+q) \bmod n}$

Here is the correct way to multiply $a^3b^1$ by $a^2b^1$ in $D_{7,2}$. First rewrite the $ba$ in the middle as $a^6b$.

$(a^3b^1)(a^2b^1) = (a^3b^0)(ba)(a^1b^1) = (a^3b^0)(a^6b^1)(a^1b^1)$

Since $a^3a^6 = a^{(3+6) \bmod 7} = a^2$, the first two factors collapse into $a^2b^1$.

$(a^3b^0)(a^6b^1)(a^1b^1) = (a^2b^1)(a^1b^1)$

Clean up the remaining product the same way.

$(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$

So $(a^3b^1)(a^2b^1) = a^1b^0$.

Given $m$, $n$, and two elements $a^jb^k$ and $a^pb^q$ of $D_{m,n}$, write a program that computes their product.

The input consists of several problem sets.

The first line of each problem set contains a problem ID and $m$, $n$, $p$, separated by spaces. The problem ID is a string of uppercase letters and digits with no spaces, $m$ and $n$ are integers between $2$ and $1000$, and $p$ is the number of multiplication questions in that set. Each of the next $p$ lines holds one question, two elements of $D_{m,n}$ separated by a space. An element is written as the letter a, an exponent, the letter b, and an exponent run together, like a3b1, and the exponents carry no leading zeros.

One problem set is followed immediately by the next. A line whose problem ID is ZZ marks the end of the input, and the rest of that line is ignored.

For each multiplication question, print one line in this format.

ProblemID id: ajbk * apbq = arbs

id is the problem ID of that set, ajbk and apbq are the two input elements copied exactly as they were given, and arbs is their product. Write the result exponents so that $0 \le r < m$ and $0 \le s < n$, and put a single space after the colon and on both sides of * and =.