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