Вовчику набридло самому рахувати яблука і абрикоси, тому він згадав, що у нього вже є робот. Як Вовчик назвав свого робота – невідомо, але ми його назвемо Марвін. Хоч Марвін і дуже здібний робот, але він вміє рахувати яблука тільки у n-ковій системі числення, а абрикоси тільки у m-ковій системі числення.

Усього Вовчик наказав виконати роботу k операцій у такому вигляді: спочатку іде символ 'a', якщо робот має перекласти яблука, і 'b', якщо абрикоси та через пробіл кількість фруктів у відповідній системі числення.

Для здійснення контролю над роботом Вовчик хоче, щоб після кожної дії Марвін виводив на екран кількість яблук і абрикос, які він уже склав у корзини, але, звичайно, у десятковому форматі.

Так як Вовчик уже студент, то в нього немає часу займатися такими легкими задачами, а вам не заважала б практика, оскільки ви самі, скоріш за все, будете писати МАН, тому саме вам необхідно допомогти Вовчику.

Програма читає із стандартного пристрою введення. У першому рядку три цілі числа k (1 <= k <= 10⁴), n, m (2 <= n, m <= 16) через пробіл. Далі у k рядках ідуть операції, довжина числа у яких не перевищує 5 символів. Програма виводить у пристрій стандартного виведення k рядків, у кожному по два цілих числа – кількість яблук і кількість абрикос через пробіл у десятковій системі числення. Гарантується, що відповідь вміщується в 64-бітний знаковий цілочисельний тип.