AA AB
AB BB
B AA
4 AB AAAB

Possible Output for Sample Input

2 1 BB
3 1 AAB
3 3 AAAA
1 3 AAAB

Explanation of Output for Sample Input

This is the example outlined in the problem description. Note that the following is another possible valid substitution sequence:

2 1 BB
3 2 BAA
1 2 BAB
3 1 AAAB

Specifically, showing the substitutions in bold , we get

\[\displaystyle \textbf{AB} \to B\textbf{B} \to B\textbf{AA} \to \textbf{B}AB \to AAAB.\]