Brainf**k 인터프리터

문제

Brainf**k 프로그램이 주어졌을 때, 이 프로그램이 종료되는지 아니면 무한 루프에 빠지는지 판정하는 프로그램을 작성하시오. 무한 루프란 어느 시점부터 빠져나오지 못하고 무한히 반복되는 루프를 말한다.

Brainf**k 인터프리터는 부호 없는 8비트 정수(값은 $256$으로 나눈 나머지로 다룬다)를 담는 배열 하나와, 그 배열의 한 칸을 가리키는 포인터로 이루어진다. 프로그램은 다음 여덟 개의 명령어로 이루어진다.

명령어	의미
`-`	포인터가 가리키는 값을 1 감소시킨다 ($256$으로 나눈 나머지).
`+`	포인터가 가리키는 값을 1 증가시킨다 ($256$으로 나눈 나머지).
`<`	포인터를 왼쪽으로 한 칸 옮긴다.
`>`	포인터를 오른쪽으로 한 칸 옮긴다.
`[`	포인터가 가리키는 값이 0이면, 짝을 이루는 `]`의 다음 명령으로 점프한다.
`]`	포인터가 가리키는 값이 0이 아니면, 짝을 이루는 `[`의 다음 명령으로 점프한다.
`.`	포인터가 가리키는 값을 출력한다.
`,`	문자 하나를 읽어 포인터가 가리키는 칸에 저장한다. 입력의 끝(EOF)이면 255를 저장한다.

인터프리터는 첫 번째 명령부터 실행한다. 한 명령을 실행한 뒤에는 다음 명령으로 넘어가되, [와 ]는 대신 점프할 수 있다. 더 이상 실행할 명령이 없으면 프로그램은 종료된다.

배열의 크기는 입력으로 주어지는 값을 사용한다. 프로그램 실행 전에 모든 칸의 값은 0이고, 포인터는 0번 칸을 가리킨다. 포인터가 배열의 양 끝을 벗어나면 반대쪽으로 돌아온다. 즉, 0번 칸에서 왼쪽으로 가면 (배열의 크기 $- 1$)번 칸으로, 마지막 칸에서 오른쪽으로 가면 0번 칸으로 간다.

[와 ]는 루프를 이루며 중첩될 수 있다. 주어지는 프로그램은 항상 올바른 형태임이 보장된다. 즉, 왼쪽에서 오른쪽으로 훑을 때 [의 개수에서 ]의 개수를 뺀 값은 항상 $0$ 이상이고, 끝까지 훑으면 $0$이 된다.

이 문제는 프로그램이 무한 루프에 빠지는지만 판정하면 되므로, 프로그램이 만드는 출력은 무시한다.

입력

첫째 줄에 테스트 케이스의 개수 $t$ ($0 < t \le 20$)가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에는 $sm$, $sc$, $si$가 주어지는데, 각각 배열의 크기, 프로그램 코드의 크기, 입력의 크기이다 ($0 < sm \le 100000$, $0 < sc, si < 4096$).

둘째 줄에는 $sc$개의 문자로 이루어진 Brainf**k 프로그램이 주어진다.

셋째 줄에는 프로그램의 입력이 주어진다 (공백이 아닌 출력 가능한 문자만 주어진다).

출력

각 테스트 케이스마다, 프로그램이 종료되면 "Terminates"를, 무한 루프에 빠지면 "Loops"를 출력한다. 무한 루프에 빠질 때는 프로그램의 어느 부분이 무한 루프인지도 함께 출력한다. 즉, 짝을 이루는 [와 ]의 위치(프로그램 안에서 0부터 세는 위치)를 공백으로 구분하여 "Loops i j" 형태로 출력한다.

프로그램이 명령어를 50,000,000개 이상 실행했다면, 그 프로그램은 반드시 종료되었거나 무한 루프에 빠져 있다. 무한 루프에 빠진 경우 그 루프는 이미 적어도 한 번의 반복을 마친 상태이며, 무한 루프 한 번의 반복에서 실행되는 명령어 수는 50,000,000개 이하이다.