Hide

# Nullary Computer

Brian Huck has invented a new power-saving computer. With the current CMOS-based processors, a certain amount of power is lost each time a bit is changed from $0$ to $1$ or back. To avoid this problem, Brian’s new Nullary Core stores only zeros. All numbers are stored in nullary form, as shown in the following table.

 Decimal Nullary 0 1 0 2 00 3 000 4 0000 5 00000 ... ...

His initial $64$-nit model has $26$ registers, each of which may store up to (and including) $64$ nits, and any attempt to store more than $64$ nits will result in a run time error. There is also a flag register, which contains either a zero, or nothing. The instruction set is as follows:

 Instruction Explanation and how to simulate in C A Add a zero to the value in register A (similarly for all uppercase letters). a++; a First, empty the flag register. Then, if possible, remove a zero from register A, and place it in the flag register (similarly for all lowercase letters) flag = 0; if(a>0) { flag=1; a--; } ( If the flag register is empty, jump past the matching ). Otherwise, empty the flag register. while(flag) { flag=0; .... ) Jump to the matching (. ... }

Apart from instructions, no other characters than whitespace (which are ignored) are allowed in a nullary program.

To illustrate the elegance and simplicity of his computer, Brian has provided the following two example programs.

 b(b)a(Ba) Move register A to register B (by first emptying register B, then repeatedly pulling a single zero from register A and placing it into B). XXXa(GIa)i(g(FY g)y(Gy)f(Zb(z)z (i(YBi)y(Iy))f) Zb(zb)z(xz)i)x Set the flag register if the number of zeros in register A is prime.

Your task is to write a sorting program for Brian’s Nullary Core-based Prototype Computer. The NCPC has limited memory, so your program must be no longer than $5432$ instructions. Also, the running time of your program must be no more than $5 \cdot 10^6$ steps for any possible input, where a step is considered to be the execution of one instruction.

The numbers to be sorted will be given in the first $24$ registers A-X; the remaining two registers (Y and Z) will be empty. After executing your sorting program, the sorted numbers should be in registers A through X, in increasing order. Registers Y and Z should be empty.

For example, if at the start of execution of your program the register values are as follows:

 Reg. Value Reg. Value Reg. Value A 0 J 000 S B 000000000 K T C 000000 L U D 0000 M V E 00000000 N W F 0000000 O X 0 G 0000 P Y H 000000 Q Z I 000000000 R

Then after executing your program, the register values should be

 Reg. Value Reg. Value Reg. Value A J S 000000 B K T 000000 C L U 0000000 D M V 00000000 E N 0 W 000000000 F O 0 X 000000000 G P 000 Y H Q 0000 Z I R 0000

Note: any error with your Nullary program, whether it be syntactically incorrect, runs for too long, or crashes, will all result in a “Wrong Answer” judgement on Kattis, but detailed information about the cause of the error will be provided in the details for your submission.

## Input

This problem has no input.

## Output

Output the nullary source code of your sorting program.

CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 6.4hard
Statistics Show
Author