Діедральна група являє собою множину \textbf{D з} мультиплікативною операцією \textbf{*}, визначеною на \textbf{D}. Множина \textbf{D} генерується двома елементами \textbf{a} та \textbf{b}. Операція множення \textbf{*} явно записуватись не буде, тобто \textbf{a*a} буде позначатись як \textbf{aa} або \textbf{a^2}. Аналогічно \textbf{a*a*b} буде записано як \textbf{a^2b^1} або просто \textbf{a^2b}. Діедральна група \textbf{D} має два цілочисельних параметри \textbf{m} та \textbf{n}, де \textbf{m }≥ \textbf{2 і} \textbf{n }≥ \textbf{2}, таким чином діедральну групу можна записати у вигляді \textbf{D_\{m,n\}}. Відношення, які визначають \textbf{D_\{m,n\}}, наступні: \textbf{a^m = a^0 = 1}, \textbf{b^n = b^0 = 1 }и \textbf{ba = a^\{(m-1)\}b}. Група \textbf{D_\{m,n\}} містить \textbf{(mn)} елементів, а саме \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)\} \}}. Наприклад, нехай \textbf{m = 7} і \textbf{n = 2}. Елементи \textbf{D_\{7,2\}} мають вигляд \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 \}}. Множення не комутативне, тобто \textbf{ba} ≠ \textbf{ab}. Насправді \textbf{ba = a^6b} згідно відношень, які визначають \textbf{D_\{7,2\}}. Також \textbf{a^ja^k = a^\{(j+k)\%m\}} і \textbf{b^jb^k = b^\{(j+k)\%n\}}. Таким чином \textbf{(a^jb^k)(a^pb^q) ≠ (a^\{(j+p)\%m\}b^\{(k+q)\%n\})}. Щоб правильно помножити два числа \textbf{(a^3b^1)} та \textbf{(a^2b^1)} із \textbf{D_\{7,2\}}, поступимо наступним чином: \textbf{(a^3b^1)(a^2b^1) = (a^3b^0)(ba)(a^1b^1) = (a^3b^0)(a^6b^1)(a^1b^1)}, так як \textbf{ba = a^6b}. Оскільки \textbf{a^3b^0a^6 = a^3a^6 = a^\{(3+6)\%7\} = a^2}, то можна знайти добуток перших двох співмножників, отримавши \textbf{(a^3b^0)(a^6b^1) = (a^2b^1)}. Таким чином \textbf{(a^3b^0)(a^6b^1)(a^1b^1) = (a^2b^1)(a^1b^1)}. Перепишемо вираз у вигляді \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)}. Результатом добутку двох елементів \textbf{(a^3b^1)} та \textbf{(a^2b^1)} буде \textbf{(a^3b^1)(a^2b^1) = (a^1b^0)}. Вам потрібно написати програму, яка за заданими \textbf{m}, \textbf{n} і довільними двома елементами \textbf{(a^jb^k)} та \textbf{(a^pb^q)} з діедральної групи \textbf{D_\{m,n\}} коректно обчислить їх добуток. \InputFile Вхідні дані складаються з декількох тестів. Кожен тест розміщується у декількох рядках. Перший рядок кожного тесту містить \textbf{problemID}, \textbf{m}, \textbf{n} та \textbf{p}, відокремлені пропуском. Значення \textbf{m} та \textbf{n }не перевищують \textbf{1000}. Число \textbf{p }вказує на кількість прикладів на множення у поточному тесті. Далі йде \textbf{p} рядків, кожен з яких містить два елементи з \textbf{D_\{m,n\}}, які потрібно перемножити. Кожен елемент буде задано у вигляді \textbf{a3b1} замість \textbf{a^3b^1}. Дані для наступного тесту йдуть відразу за попереднім. Якщо \textbf{problemID} дорівнює "\textbf{ZZ}", то це позначає кінець вхідних даних. \OutputFile Для кожного прикладу на множення потрібно вивести один рядок виду \textbf{ProblemID id: ajbk * apbq = arbs} де \textbf{id }- номер заданої на вході \textbf{problemID}, \textbf{ajbk} та \textbf{apbq} - елементи, які потрібно перемножити, а \textbf{arbs} - коректна відповідь.