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