Задача 3O. Turing Machine ≡

Условие

Требуется выполнить программу для детерминированной машины Тьюринга.

Пусть задана машина Тьюринга с алфавитом A = {i}N − 1i = 0 и множеством состояний S = {i}Mi = 0. Программа, которую требуется выполнить, описывается тройками значений для каждой пары "символ" / "состояние"

1. Символ, который требуется записать на ленту;
2. Направление движения указателя машины: "L" — влево, "R" — вправо, "N" — не сдвигать указатель;
3. Состояние, в которое переходит машина.

Программа исполняется на бесконечной ленте заполненной символом 0. Изначально машина находится в состоянии 0 на позиции 0 и заканчивает работу при достижении состояния M.

Формат входных данных

Первая строка входных данных содержит натуральные числа N, M, K — размер алфавита, множества состояний и входных данных программы. Далее следуют N строк по M троек — описание программы. Строка i + 2 содержит тройки для символа i, перечисленные по возрастанию номера состояния. Последняя строка файла содержит текущие состояние ленты длины K.

Формат выходных данных

Выходные данные должны содержать состояние ленты начиная с позиции указателя, в которой машина завершила работу, до последней ячейки, посещённой указателем.

Ограничения

Примеры тестов

3 3 8
0 N 3  1 R 1  0 L 2
1 N 3  0 R 1  1 L 2
2 R 1  2 L 2  2 N 3
2 0 1 0 1 0 1 2

2 1 0 1 0 1 0 2

2 4 3
1 R 1  1 L 0  1 L 1  1 N 4
1 L 2  1 R 1  1 L 3  1 L 3
0 0 0

1 1 1 1 1 1 1

4 12 4
0 N 12  0 R  1  3 L  3  0 L  3  3 R 5  0 R 5  0 R 6  0 R  7  0 R  8  0 N 12  0 R 10  0 L 11
1 N 12  1 R  1  1 N 12  1 L  3  3 R 6  1 R 5  1 R 6  1 R  7  1 R  8  1 N 12  1 R 10  1 L 11
2 R  1  2 R  2  2 N 12  2 L  4  2 R 9  2 R 7  2 R 8  2 N 12  2 N 12  2 R 10  2 N 12  2 N 12
3 N 12  3 N 12  3 N 12  3 N 12  3 L 4  3 R 5  3 R 6  0 R  2  1 R  2  2 R  9  2 L 11  3 N 12
2 1 0 2

2 0 1 2