BrainFuckVM
Дана программа на языке brainfuck. Ваша задача — определить, завершится ли она или войдет в бесконечный цикл. Интерпретатор brainfuck использует массив данных, состоящий из беззнаковых 8-битных целых чисел, и индекс, называемый "индексом данных". Элемент массива, на который указывает индекс данных, называется "текущим элементом". Программа на brainfuck представляет собой последовательность из восьми возможных инструкций:
Выполнение программы начинается с первой инструкции и продолжается до тех пор, пока указатель инструкции не выйдет за пределы программы. После выполнения каждой инструкции указатель перемещается к следующей справа, за исключением случаев, когда инструкции цикла [ или ] изменяют этот порядок.
Помимо программы, вам будет предоставлен размер массива данных. Элементы массива данных — это беззнаковые 8-битные целые числа с обычным поведением при переполнении и недополнении. В начале выполнения программы все элементы массива данных и индекс данных инициализируются нулем.
Если индекс данных выходит за пределы массива, он должен быть перенесен на противоположный край массива; например, если индекс данных уменьшается, когда он равен нулю, он должен быть установлен в значение "размер массива данных минус один".
Инструкции [ и ] обозначают циклы и могут быть вложенными. Каждая программа будет корректной, то есть при последовательном чтении программы слева направо количество инструкций [ минус количество инструкций ] всегда будет больше или равно нулю, и в конце программы оно будет равно нулю.
Для этой задачи игнорируйте вывод программы^1.
____________
^1 Для целей отладки вы можете его изучить. Третья программа из примера ввода напечатает "ICPC"; четвертая программа, при подаче произвольной строки, напечатает программу на brainfuck, которая, в свою очередь, напечатает эту произвольную строку при выполнении.
Входные данные
Ввод начинается с одной строки, содержащей количество тестов t (0 < t ≤ 20). Каждый тест состоит из трех строк. Первая строка содержит три целых числа sm, sc, si, которые описывают размер памяти, размер кода программы и размер ввода (0 < sm ≤ 100 000; 0 < sc, si < 4 096).
Вторая строка содержит код программы на brainfuck, который необходимо выполнить; он состоит из sc символов. Третья строка содержит ввод программы в виде текста (только печатные, не пробельные символы). Как только программа использует весь доступный ввод, инструкция ввода должна установить текущую ячейку в 255.
Выходные данные
Для каждого теста выведите одну строку: "Terminates", если программа завершится после конечного числа шагов, или "Loops", если она войдет в бесконечный цикл. Если программа зацикливается, также укажите индексы (0-based) двух символов [ и ] в массиве кода, которые соответствуют бесконечному циклу. Вы можете предположить, что после 50 000 000 инструкций программа либо завершится, либо зациклится в бесконечном цикле, который будет выполнен хотя бы один раз. Во время каждой итерации бесконечного цикла выполняется не более 50 000 000 инструкций.