Multiplication in a Dihedral Group
A dihedral group is a set D with a multiplication operation * defined on D. The set D is generated by two elements a and b. The multiplication operation * will not be explicitly written, so that a*a will be indicated by aa or by a^2. Similarly, a*a*b will be indicated by a^2b^1 or simply a^2b.
The dihedral group D has two integer parameters m and n, with m ≥ 2 and n ≥ 2, and so we write the dihedral group as D_{m,n}. The relations that define D_{m,n} are:
a^m = a^0 = 1, b^n = b^0 = 1, and ba = a^{(m-1)}b.
Thus D_{m,n} has (mn) elements, namely
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)} }.
For example, select m = 7 and n = 2. The elements of D_{7,2} are
{ 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 }.
Multiplication is not commutative, and so ba ≠ ab. In fact ba = a^6b, according to the defining relations of D_{7,2}. Also, a^ja^k = a^{(j+k)%m}, and b^jb^k = b^{(j+k)%n}. Thus
(a^jb^k)(a^pb^q) ≠ (a^{(j+p)%m}b^{(k+q)%n}).
To properly multiply the two elements (a^3b^1) and (a^2b^1) of D_{7,2}, we proceed as follows,
(a^3b^1)(a^2b^1) = (a^3b^0)(ba)(a^1b^1) = (a^3b^0)(a^6b^1)(a^1b^1),
since ba = a^6b.
Also, since a^3b^0a^6 = a^3a^6 = a^{(3+6)%7} = a^2, we can multiply the first two factors and get (a^3b^0)(a^6b^1) = (a^2b^1).
Thus
(a^3b^0)(a^6b^1)(a^1b^1) = (a^2b^1)(a^1b^1).
Now we can rewrite this as follows,
(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).
Thus, multiplying the two elements (a^3b^1) and (a^2b^1) gives, (a^3b^1)(a^2b^1) = (a^1b^0).
Your problem is to write a computer program, given m, n, and any two elements (a^jb^k) and (a^pb^q) of the dihedral group D_{m,n} that computes the correct product of the two.
Input
The input consists of several problem sets. Each problem set consists of several lines of input. The first line will contain the problemID, m, n, and p, separated by spaces. The integers m and n will not exceed 1000 in value. The number p is the number of multiplication problems for this problem set. The first line is followed by p lines of input, each line containing two elements of D_{m,n} to multiply. Each element will be given in the form a3b1 instead of a^3b^1. Data for the next problem set will immediately follow the previous problem set. A set problemID of "ZZ" will indicate end of input.
Output
For each multiplication problem, print one line of the form
ProblemID id: ajbk * apbq = arbs
where id is the problemID given in the input, ajbk and apbq are the elements to multiply, and arbs is the correct answer.