H. RSC-IV (Redstone Computer 4)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

BlockInstructionEffect
AINCAdd 1 to the value in the register, then increment the instruction pointer
BDUBDouble the value in the register, then increment the instruction pointer
CJMPIncrease the instruction pointer by $$$R$$$, where $$$R$$$ is the value in the register
DPUTPut/append the value in the register into the output as a block, where 0=A, 1=B, 2=C, and 3=D, then increment the instruction pointer

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.
If the task is impossible, just print "C", a program that immediately halts.
Input

The first and only line contains an output string $$$S$$$ $$$(1 \le |S| \le 100)$$$ consisting only of $$$A$$$s, $$$B$$$s, $$$C$$$s, and $$$D$$$s.

Output

Print a program string $$$P$$$ $$$(|P| \le 1000)$$$ which will print exactly $$$S$$$ and contains $$$S$$$ as a substring. Print "C" if the task is impossible.

Examples
Input
AAAA
Output
AAAABBBBDDDDC
Input
ABCDA
Output
ABCDABBBBDADBBAADBAAADADC
Input
DADADADADA
Output
C