Brainf*ck Interpreter

Time limit1sMemory limit128 MB

Summary

Implement a Brainfsck interpreter that parses a program per test case, checks bracket matching, and executes it printing output or a compile error.

Level: Medium4 of 10
Topics: Stack, Simulation, Implementation
Solved: No attempts yet

Problem

Brainf*ck is a small Turing-complete programming language designed more for challenge and amusement than practical use. In this problem, you must interpret a version of the language that has no input instruction.

The language uses a byte array of length 32768, initialized to 0, and a pointer that initially points to the first byte. Each byte stores a value from 0 to 255.

The seven commands used in this problem are one character each.

>: Move the pointer one cell to the right. If it is at 32767, it wraps to 0.
<: Move the pointer one cell to the left. If it is at 0, it wraps to 32767.
+: Increase the current byte by 1. Increasing 255 wraps it to 0.
-: Decrease the current byte by 1. Decreasing 0 wraps it to 255.
.: Output the current byte as an ASCII character.
[: If the current byte is 0, jump to the matching ] after it.
]: If the current byte is not 0, jump back to the matching [ before it.

Given a Brainf*ck program, print the output produced by that program.

Input

The first line contains the number of programs T (1 <= T <= 100). Each program consists of one or more lines and ends with a line containing only end. Characters other than the command characters (<>+-.[]) are ignored. A % starts a comment, so every character after % on that line is ignored. One program contains at most 128000 executable commands.

Output

For each program, first print PROGRAM #n:, where n is the 1-based program number. Then print the program output. If the brackets [ and ] are not matched correctly, print COMPILE ERROR instead of running the program. A program output may span multiple lines.

Examples1

Example 1

Input

3
++++++++[>+++++++++ % hello-world.
<-]>.<+++++[>++++++<-]>-.+++++++..
+++.<++++++++[>>++++<<-]>>.<<++++[>
------<-]>.<++++[>++++++<-]>.+++.
------.--------.>+.
end
+++[>+++++++[.
end
%% Print alphabet, A-Z.
+ + + + + +++++++++++++++++++++>
++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++
+< [ >.+<- ]
end

Expected output

PROGRAM #1:
Hello World!
PROGRAM #2:
COMPILE ERROR
PROGRAM #3:
ABCDEFGHIJKLMNOPQRSTUVWXYZ