Delightful (Hard)

Time limit1sMemory limit512 MB

Summary

Write a program of at most 5000 commands for a ternary computer with 26 forty-trit registers that sets Y to 1 if the input X (0 to 109) is prime and 0 otherwise.

Level: Hard9 of 10
Topics: Number theory, Implementation, Brute force, Math
Solved: No attempts yet

Problem

You found a strange box in your grandma's basement. A closer look revealed it to be an old-school computer. You tried running a few simple programs, but they all behaved very strangely. It took you a while to pin down the cause: this computer uses ternary logic and arithmetic!

A trit is the ternary counterpart of a bit. A trit can store the values 0, 1, and 2. When performing logical operations on trits, we treat 0 as false, 1 as unknown, and 2 as true.

The computer has 26 registers, labeled A through Z. Each register is a 40-trit unsigned integer variable.

When your program starts executing, register X holds the input number and every other register holds zero. X is guaranteed to be between 0 and 109, inclusive.

Write a program that sets Y to 1 if X is prime, and leaves it at 0 if it is not. (Recall that 0 and 1 are not prime.)

Your program must contain at most 5,000 commands.

Input

There is no input.

Output

Your output file must contain a program that meets the requirements above and solves the given subproblem.

Empty lines and extra whitespace on each line are ignored, so you may use them freely to format your program for readability. Only non-empty lines count toward the instruction limit. Remember that there must be at least one space between any two tokens in your program, and at least one newline between any two commands.

Examples1

Example 1
Input
Expected output
```
A = X - 1
B = ~ A
C = B ^ X
X = X & C
```