정이면체군의 곱

정이면체군은 곱셈 연산 $*$가 정의된 집합 $D$이다. $D$의 원소는 모두 두 원소 $a$와 $b$로 만든다. 곱셈 기호는 거의 쓰지 않고 두 원소를 붙여 쓰거나 지수로 줄여 쓴다. 즉 $a*a$는 $aa$ 또는 $a^2$으로 쓰고, $a*a*b$는 $a^2b^1$ 또는 $a^2b$로 쓴다.

정이면체군 $D$는 파라미터 $m$과 $n$을 받고, $m \ge 2$, $n \ge 2$이다. 이 군을 $D_{m,n}$으로 쓴다. $D_{m,n}$에서는 다음 세 관계가 성립한다.

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

따라서 $D_{m,n}$의 원소는 모두 $mn$개다.

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

$m = 7$, $n = 2$이면 $D_{7,2}$는 다음 14개 원소로 이루어진다.

$\{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 \ne ab$이다. $D_{7,2}$에서는 $ba = a^6b$이다. 같은 문자의 거듭제곱은 $a^ja^k = a^{(j+k) \bmod m}$, $b^jb^k = b^{(j+k) \bmod n}$으로 합쳐지지만, 두 문자가 섞이면 지수를 그냥 더할 수 없다.

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

$D_{7,2}$의 두 원소 $a^3b^1$과 $a^2b^1$을 올바르게 곱하는 과정은 다음과 같다. 먼저 가운데의 $ba$를 $a^6b$로 바꾼다.

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

$a^3a^6 = a^{(3+6) \bmod 7} = a^2$이므로 앞의 두 원소는 $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^1b^0$이다.

$m$과 $n$, 그리고 $D_{m,n}$의 두 원소 $a^jb^k$와 $a^pb^q$가 주어졌을 때 곱한 결과를 구하는 프로그램을 작성하시오.

입력은 여러 개의 문제 세트로 이루어진다.

각 문제 세트의 첫째 줄에는 문제 ID와 $m$, $n$, $p$가 공백으로 구분되어 주어진다. 문제 ID는 대문자와 숫자로 이루어진 공백 없는 문자열이고, $m$과 $n$은 $2$ 이상 $1000$ 이하의 정수이며, $p$는 그 세트에 들어 있는 곱셈 문제의 개수다. 다음 $p$개 줄에는 곱셈 문제가 한 줄에 하나씩 주어지고, 각 줄에는 $D_{m,n}$의 원소 두 개가 공백으로 구분되어 주어진다. 원소는 a3b1처럼 문자 a, 지수, 문자 b, 지수를 이어 붙인 형식이고 지수에 앞자리 0은 붙지 않는다.

한 문제 세트가 끝나면 바로 다음 문제 세트가 이어진다. 문제 ID가 ZZ인 줄은 입력의 끝을 뜻하고, 그 줄의 나머지 값은 무시한다.

각 곱셈 문제마다 한 줄에 다음 형식으로 출력한다.

ProblemID id: ajbk * apbq = arbs

id는 그 문제 세트의 문제 ID, ajbk와 apbq는 입력으로 주어진 두 원소를 입력에 적힌 그대로 옮긴 것, arbs는 두 원소를 곱한 결과다. 결과의 지수는 $0 \le r < m$, $0 \le s < n$을 만족하는 값으로 적고, 콜론 뒤와 *, = 양옆에는 공백을 하나씩 둔다.