Диэдральная группа представляет собой множество \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} - корректный ответ.