Brainf**k Interpreter

Time limit7sMemory limit128 MB

Summary

Decide whether a given Brainfuck program halts on its input and, if it loops, report the matching bracket pair that encloses the infinite loop.

Level: Hard9 of 10
Topics: Simulation, Implementation, Stack, Brute force
Solved: No attempts yet

Problem

Given a Brainf**k program, determine whether it terminates or falls into an infinite loop. An infinite loop is a loop that, from some point on, keeps repeating forever without ever leaving.

A Brainf**k interpreter has a single array of unsigned 8-bit integers (values are taken modulo $256$ ) and a pointer to one cell of that array. A program is a sequence of the following eight commands:

Command	Meaning
`-`	Decrease the value at the pointer by 1 (modulo $256$ ).
`+`	Increase the value at the pointer by 1 (modulo $256$ ).
`<`	Move the pointer one cell to the left.
`>`	Move the pointer one cell to the right.
`[`	If the value at the pointer is 0, jump to the command after the matching `]`.
`]`	If the value at the pointer is not 0, jump to the command after the matching `[`.
`.`	Output the value at the pointer.
`,`	Read one character and store it at the pointer; on end of input (EOF) store 255.

The interpreter starts at the first command. After running a command it moves to the next one, except that [ and ] may jump instead. When there is no command left to run, the program terminates.

The tape size is the value given in the input. Before the program runs, every cell is 0 and the pointer is at cell 0. When the pointer moves past either end of the tape it wraps around to the other end: moving left from cell 0 lands on cell (tape size $- 1$ ), and moving right from the last cell lands on cell 0.

[ and ] form loops and may be nested. The given program is guaranteed to be well-formed: scanning left to right, the number of [ seen minus the number of ] seen is always $\ge 0$ , and equals $0$ at the end.

This problem only asks whether the program falls into an infinite loop, so any output the program produces is ignored.

Input

The first line contains the number of test cases $t$ ( $0 < t \le 20$ ). Each test case consists of three lines. The first line contains $sm$ , $sc$ , $si$ : the tape (array) size, the program code size, and the input size ( $0 < sm \le 100000$ , $0 < sc, si < 4096$ ).

The second line contains the Brainf**k program, which is $sc$ characters long.

The third line contains the program's input (only printable, non-space characters).

Output

For each test case, print "Terminates" if the program terminates, or "Loops" if it falls into an infinite loop. When it loops, also print which part of the program is the infinite loop: the positions of the matching [ and ] (0-indexed within the program), separated by spaces, as "Loops i j".

If a program runs at least 50,000,000 commands it is guaranteed to have either terminated or entered an infinite loop. When it loops, that loop has already completed at least one full iteration, and a single iteration of the infinite loop runs at most 50,000,000 commands.

Examples1

Example 1

Input

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

Expected output

Terminates
Loops 1 4
Terminates
Terminates