Statistics

You're running a special TopCoder competition where all programs are written in a derivative of a restrictive language called Unefunge, and all programs must complete in under 80,000 cycles. Furthermore, all programs are required to be Quines. For the purpose of this problem, a Quine is a special type of program that prints out its own source code before it prints anything else. Thus, in order for the Unefunge program ":,:9#@_1+" to be a legal program it would first have to print the string ":,:9#@_1+".

The language Unefunge works like this: a program is just a single line of characters of length N, where N is between 1 and 50 inclusive. The program never changes. An instruction pointer starts with the value 0 (called the IP), a delta is given the value 1 (called D), and an empty stack is created. The stack will store integer values during program execution in a first-in-last-out manner; if a number is pushed, it is placed in the stack, and if a value is popped, the last number pushed is removed (or a 0 is popped if the stack is empty). During each cycle, the IPth character in the program is read, the instruction corresponding to that character is executed, and then IP is incremented to the new value (3*N+IP+D)%N. The instructions are as follows:

• '0'-'9': pushes the number represented by that digit onto the stack.
• '$' : pops a value off the stack, and discards it.
• ':' : pops a value off the stack, then pushes that same value onto the stack twice.
• 'W' : Pops a value A, then pops a value B, then pushes A, then pushes B.
• ',' : pops a value X off of the stack, and prints the (absolute value of X)%Nth character in the source code.
• '+' : pops two values, adds them, and pushes the result back onto the stack.
• '-' : pops two values, subtracts the second popped value from the first, and pushes the result back onto the stack.
• '#' : multiplies D by 2 for this cycle only.
• 'R' : multiplies D by -1.
• 'S' : pops a value, and if positive pushes a 1, else pushes a -1.
• '_' : pops a value X, and sets D to that value X%N.
• 'J' : pops a value X, and sets IP to the (absolute value of X)%N. (IP is not incremented after this step)
• '@' : stops the program

You have to write a program that takes a String source and checks whether or not the program being submitted is valid. If the program doesn't end in 80,000 cycles or less, return "TIMEOUT". Otherwise you'll return a message with the ending condition replacing X with the cycle number in which this ending condition is reached.

• If the program ends before printing out its source, return the string "BADEND X".
• If a number less than -1000000000 or a number greater than 1000000000 is pushed onto the stack, return "OVERFLOW X".
• If the result of an instruction makes it impossible for the output to match the source code, return "MISMATCH X".
• If the result of an instruction makes the output match the source code, return "QUINES X".