Kattis

BrainFsckVM

Given a brainfsck program, determine whether it terminates or enters an endless loop.

A brainfsck interpreter has a data array (consisting of unsigned 8-bit integers) with an index, the so called “data index”; the entry of the array pointed to by the data index is the so called “current entry”. A brainfsck program consists of a sequence of the following eight instructions:

 - decrease current entry by $1$ (modulo $2^8$) + increase current entry by $1$ (modulo $2^8$) < decrease data index by $1$ > increase data index by $1$ [ jump behind the matching ], if the current entry is equal to 0 ] jump behind the matching [ if the current entry is not equal to $0$ . print the current entry as character , read a character and save it into the current entry. On end of input save $255$.

Interpretation of a brainfsck program starts at the first instruction, and terminates if the instruction pointer leaves the end of the program. After an instruction is executed, the instruction pointer advances to the instruction to the right (except, of course, if the loop instructions [ or ] cause a jump).

In addition to the program, you will be given the size of the data array. The entries of the data array shall be unsigned 8-bit integers, with usual over- or underflow behaviour. At the start of the program, the data array entries and the data index shall be initialized to zero.

Incrementing or decrementing the data index beyond the boundaries of the data array shall make it re-enter the data array at the other boundary; e.g. decrementing the data index when it is zero shall set it to the size of the data array minus one.

The [ and ] instructions define loops and are allowed to nest. Every given program will be well-formed, i.e. when traversing the program from left to right, the number of [ instructions minus the number of ] instructions will always be greater or equal zero, and at the end of the program it will be equal to zero.

For the purposes of the problem, discard the output of the interpreted program. 1

Input

The input starts with a line containing the number of test cases $t$ ($0 < t \le 20$). Each test case consists of three lines. The first line contains three integers $s_ m, s_ c, s_ i$, describing the size of the memory, the size of the program code and the size of the input ($0 < s_ m \le 100\, 000; 0 < s_ c, s_ i < 4\, 096$).

The second line contains the brainfsck program code to be executed; it consists of $s_ c$ characters.

The third line contains the input of the program, as text (only printable, non-whitespace characters). Once the program has consumed all available input, the input instruction shall set the current cell to $255$.

Output

For each test case, print one line, containing either “Terminates” or “Loops”, depending on whether the program either terminates after a finite number of steps, or enters an endless loop. If the program loops, also print the indices ($0$-based) of the two [ and the ] symbols in the code array that correspond to the endless loop. You may safely assume that after $50\, 000\, 000$ instructions, a program either terminated or hangs in an endless loop, which then was executed at least once. During each iteration of the endless loop at most $50\, 000\, 000$ instructions are executed.

Sample Input 1 Sample Output 1
4
10 4 3
+-.,
qwe
1000 5 1
+[+-]
a
100 74 4
+++++[->++<]>[-<+++++++>]<[->+>+>+>+<<<<]>+++>--->++++++++++>---<<<.>.>.>.
xxyz
9999 52 14
+++++[>+++++++++<-],+[-[>--.++>+<<-]>+.->[<.>-]<<,+]
this_is_a_test

Terminates
Loops 1 4
Terminates
Terminates


Footnotes

1. For purposes of debugging, you may examine it. The third program from the sample input would print “ICPC”; the fourth program, when given an arbitrary string, will print a brainfsck program, that in turn will print said arbitrary string when executed.