To Add or to Multiply

The Industrial Computer Processor Company offers very fast, special-purpose processing units tailored to customer needs. Processors of the $a$-C-$m$ family (such as $1$-C-$2$ and $5$-C-$3$) have an instruction set with only two different operations:

A add $a$

M multiply by $m$

The processor receives an integer, executes a sequence of $A$ and $M$ operations (the program) that modifies the input, and outputs the result. For example, the $1$-C-$2$ processor executing the program $AAAM$ with the input $2$ yields the output $10$ (the computation is 2 \to 3 \to 4 \to 5 \to 10), while the $5$-C-$3$ processor yields $51$ with the same program and input (2 \to 7 \to 12 \to 17 \to 51).

You are an $a$-C-$m$ programmer assigned to a top secret project. This means that you have not been told the precise computation your program should perform. But you are given particular values $p$, $q$, $r$, and $s$ and the following conditions:

1. The input is guaranteed to be a number between $p$ and $q$.

2. The output must be some number between $r$ and $s$.

Given an $a$-C-$m$ processor and the numbers $p$, $q$, $r$, and $s$, your job is to construct the shortest $a$-C-$m$ program which, for every input $x$ such that p \leq x \leq q, yields some output $y$ such that r \leq y \leq s. If there is more than one program of minimum length, choose the one that comes first lexicographically, treating each program as a string of $A$s and $M$s.