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