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

Компанія Industrial Computer Processor Company пропонує дуже швидкі, спеціалізовані обчислювальні модулі, розроблені під потреби клієнтів. Процесори сімейства $a$-C-$m$ (наприклад, $1$-C-$2$ і $5$-C-$3$) мають набір інструкцій, що складається лише з двох різних операцій:

A додати $a$

M помножити на $m$

Процесор отримує ціле число, виконує послідовність операцій $A$ та $M$ (програму), які змінюють вхідне число, і видає результат. Наприклад, процесор $1$-C-$2$, виконуючи програму $AAAM$ зі входом $2$, видасть $10$ (обчислення: 2 \to 3 \to 4 \to 5 \to 10), тоді як процесор $5$-C-$3$ дає $51$ за тією ж програмою і входом (2 \to 7 \to 12 \to 17 \to 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 \leq x \leq q, дає вихідне число $y$, для якого r \leq y \leq s. Якщо існує кілька програм мінімальної довжини, оберіть ту, що йде найпершою в лексикографічному порядку, розглядаючи програму як рядок з літер $A$ та $M$.