Додати або помножити

Промислова компанія, яка виробляє процесори для комп'ютерів, пропонує дуже швидкі пристрої з опрацювання інформації з врахуванням потреб клієнтів. Множина команд процесорів серії a-C-m (таких як 1-C-2 та 5-C-3) складається усього лише з двох різних операторів:

A add a M multiply by m

На вхід процесор отримує ціле число, потім виконує послідовність з A та M операторів (програму), яка змінює вхідні дані, і виводить результат. Наприклад, процесор 1-C-2, який виконує програму AAAM на вхідному числі 2, виведе 10 (послідовність обчислень: 2 → 3 → 4 → 5 → 10), а процесор 5-C-3 виведе 51 при тій же програмі і з тими ж вхідними даними (2 → 7 → 12 → 17 → 51).

Ви - a-C-m програміст, який займається секретним проектом. Це означає, що Вам не відомі конкретні обчислення, які повинна виконувати Ваша програма. Але Вам задано деякі значення p, q, r і s, а також наступні умови:

1. Вхідним значенням є число, яке знаходиться між p і q.

2. Вихідне значення повинно бути цілим, яке лежить між r і s.

За заданими a-C-m процесором та числами p, q, r і s необхідно створити найкоротшу a-C-m програму, яка для кожного x, для якого p ≤ x ≤ q, виведе значення y, для якого r ≤ y ≤ s. Якщо існує декілька найкоротших програм, то вивести лексикографічно найменшу. Програму слід трактувати як рядок, який містить літери A та M.

Вхідні дані

Вхідні дані складаються з декількох тестів. Кожен тест задається одним рядком, який містить шість цілих чисел a, m, p, q, r і s (1 ≤ a, m, p, q, r, s ≤ 10^9, p ≤ q і r ≤ s).

Останній тест завершується рядком, який містить шість нулів.

Вихідні дані

Для кожного тесту вивести його номер та найкращу програму, як описано в умові. Вивести слово "empty", якщо найкраща програма не використовує операторів. Вивести слово "impossible", якщо не існує програми, що задовольняє специфікаціям.

Програму слід виводити у вигляді послідовності рядків, які чергуються, виду "nA" і "nM" (n > 0), відокремлених одним пропуском. Рядки першого типу означають послідовність А операторів довжини n, а рядки другого типу послідовність M операторів довжини n.

Приклади