Run the Bytecode: A Tiny Stack VM

The story

Malware analysts, game modders and language designers all meet the same shape sooner or later: a virtual machine. A program is not machine code, it is a list of bytes that a small interpreter decodes one instruction at a time. To understand such a program you first need the interpreter. Today you write it.

The STK1 machine has a stack of integers and a program counter (pc) that starts at 0. The program is a list of bytes. The machine repeats: read the opcode at pc, advance pc, execute it.

Opcodes

| Hex | Name | Operand | Effect | |---|---|---|---| | 00 | HALT | none | stop the program | | 01 | PUSH | 1 byte n (0-255) | push n | | 02 | ADD | none | pop b, pop a, push a + b | | 03 | SUB | none | pop b, pop a, push a - b | | 04 | MUL | none | pop b, pop a, push a * b | | 05 | DUP | none | push a copy of the top value | | 06 | SWAP | none | exchange the top two values | | 07 | POP | none | discard the top value | | 08 | PRINT | none | pop a value and print it in decimal followed by a newline | | 09 | PRINTC | none | pop a value and print the ASCII character with that code (no newline) | | 0A | JMP | 1 byte addr | set pc to addr | | 0B | JZ | 1 byte addr | pop a value; if it is 0 set pc to addr | | 0C | JNZ | 1 byte addr | pop a value; if it is not 0 set pc to addr | | 0D | LT | none | pop b, pop a, push 1 if a < b, else 0 | | 0E | OVER | none | push a copy of the second value from the top (a b becomes a b a) |

An operand byte follows its opcode in the program, so those instructions are two bytes long. Jump addresses are absolute positions in the program (the first byte is address 0). If a conditional jump is not taken, execution continues after its operand.

Ending the run

• Executing HALT, or running past the last byte of the program, ends it normally.
• A fault ends it at once and prints FAULT followed by a newline right after whatever was already printed. A fault is: an unknown opcode, an instruction that needs more values than the stack holds, an operand byte missing at the end of the program, or a taken jump to an address that is at or beyond the program length.
• A program that has executed 100000 instructions is stopped before the next one: print LIMIT and a newline. (Real sandboxes need such a watchdog.)

Input and output

The input is the program as hexadecimal byte values (one or two digits each, upper or lower case) separated by any whitespace, possibly across several lines. The program has at most 255 bytes, and an empty input is an empty program. Print whatever the program prints. Values fit in a signed 64-bit integer in every test.

Examples

Input:

01 03 05 08 01 01 03 05 0C 02 00

Output:

3
2
1

Read as assembly: PUSH 3, then a loop at address 2 DUP, PRINT, PUSH 1, SUB, DUP, JNZ 2, then HALT.

Input:

01 06 01 07 04 08 01 0A 01 04 03 08

Output:

42
6

Input:

01 4F 09 01 4B 09 01 0A 09

Output:

OK

The hidden tests run much more than these three: loops, text, every fault, the instruction limit and awkward formatting.

01 03 05 08 01 01 03 05 0C 02 00