Задача 3O. Turing Machine

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10, 1 ≤ M ≤ 20, 1 ≤ K ≤ 105. Максимальная длина ленты, необходимая для выполнения программы, не превышает 105.

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

Стандартный вход Стандартный выход
1
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
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
3
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

0.241s 0.129s 13