Chat, we've done it! We've made a computer... in Minecraft! The only thing is, it has a peculiar instruction set called RSC-IV, or "Redstone Computer 4". "Redstone Computer" because the logic is built with redstone, and "4" because there are only 4 values that it understands.

Because it only understands 4 values, RSC-IV only has 4 instructions that a program can contain. A program is just a 1-dimensional line of wood blocks. The only valid wood blocks are Acacia, Birch, Cherry, and Dark Oak. From here on out, we will just refer to these blocks by their first letters: A, B, C, and D.

RSC-IV has only four components.

1. A line of blocks for the input program.
2. A line of blocks for the output string. The output string consists of the same 4 wood blocks we use for the input program.
3. An instruction pointer that starts at the beginning of the program and determines the next block from the program to be interpreted.
4. A 2-bit (4-value) register that starts at the value 0.

Each block in the program is one instruction that either acts on the register, the instruction pointer, or the output. Here are the effects of the 4 program blocks:

There are three caveats to note:

• The value in the register can overflow. In this case, we still just keep the bottom 2 bits. You can think of this as $$$R = f(R)\text{ mod }4$$$ for every operation done to the register $$$R$$$.
• You may have noticed that we can do a C/JMP while our register holds the value 0. This is known as a "halt". To be a valid RSC-IV program, the program line must end with a halt – it is invalid for a program to halt before reaching the last block in the program line, and it is invalid for a program to never halt or have the instruction pointer go beyond the end of the program line.

One fun thing computer scientists like to do is make a "quine" – a program that outputs itself. We won't have you make a quine, but we'll ask for something similar. The challenge we have for you is the following: take a given output string $$$S$$$ and make a valid RSC-IV program $$$P$$$ with the following constraints:

• $$$P$$$ contains $$$S$$$ as a substring.
• Upon halting, $$$P$$$ must have produced exactly $$$S$$$ as the output string.