Сложить или умножить
Промышленная компания, выпускающая процессоры для компьютеров, предлагает очень быстрые устройства по обработке информации с учетом потребностей клиентов. Множество команд процессоров серии 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, а также следующие условия:
Входным значением является число, которое находится между p и q.
Выходное значение должно быть целым, которое лежит между 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.