Тьюринг
Недавно в архивах ACM были обнаружены интересные документы. Эти документы содержат описание оригинальной версии соревнования ACM ICPC, которое прошло в Блетчли-парке, Англия, в 1943 году.
В этом оригинальном конкурсе программы, представленные участниками, выполнялись на упрощённой версии так называемой детерминированной машины Тьюринга, с которой, несомненно, большинство из вас знакомо. В этой упрощённой версии лента не бесконечна. Вместо этого ячейки ленты пронумерованы от 0 до 10^3-1 (включительно), слева направо. Также используется унарный алфавит, что означает, что перед выполнением программы лента будет инициализирована строкой, состоящей из n единиц, за которыми следуют все нули, где n — числовое значение входных данных, а после выполнения содержимое ленты должно быть m единиц, за которыми следуют все нули, где m — числовое значение соответствующего вывода. В начале головка ленты находится в позиции 0, а состояния также пронумерованы, начиная с 0, которое считается начальным состоянием. Машины работают как обычно: для каждого состояния машины q и каждого бита c (0 или 1) существует не более одного правила, определяющего, каким будет следующее состояние, если символ в позиции головки ленты равен c, а текущее состояние — q; правило также указывает символ, который нужно записать в текущую позицию, и направление, в котором должна двигаться головка. Когда ни одно правило не применяется, машина останавливается.
Ваша задача — написать программу, которая получает одну из машин Тьюринга, представленных участниками, а также используемые тестовые случаи (входные и выходные пары) и возвращает вердикт о результатах машины для каждого из случаев. Обратите внимание, что в этом оригинальном конкурсе, в отличие от текущего, для каждого тестового случая был отдельный вердикт, а не общий.
Входные данные
Входные данные состоят из серии спецификаций (не более 30) машины Тьюринга и соответствующих тестовых случаев.
Структура каждого тестового случая следующая:
Первая строка содержит 1 ≤ N ≤ 1000, количество правил для машины, и 1 ≤ M ≤ 100, количество тестовых случаев для машины Тьюринга.
Следуют N строк, каждая из которых содержит правило в формате q_prev c_prev q_next c_next mov. q_prev — состояние машины до применения правила, c_prev — содержимое (либо 0, либо 1) ленты в текущей позиции p до применения правила, q_next — состояние машины после применения правила, c_next — содержимое позиции p после применения правила, и mov — направление, в котором головка ленты перемещается на один шаг после применения правила ("L", если она движется влево, и "R", если вправо). Состояния должны быть целыми числами от 0 до 1000 включительно. Машина Тьюринга должна быть детерминированной; то есть, должно быть не более одного перехода от любой пары (q_prev, c_prev), и не должно повторяться в вашем выводе.
После этого следуют M строк, каждая из которых содержит два числа, разделённых пробелом, X и Y, 1 ≤ X, Y ≤ 1000. X — значение входных данных для программы, а Y — значение ожидаемого вывода.
Конец ввода обозначается случаем с N = 0 и M = 0.
Выходные данные
Ваш вывод должен быть MLE, если машина пытается получить доступ к любой ячейке за пределами указанного выше диапазона ленты; TLE, если она выполняется не менее 10^4 итераций без остановки или возникновения ошибки MLE; WA, если машина останавливается, но возвращает неправильный результат, и AC, если машина останавливается и возвращает ожидаемый результат.
Вывод для каждого случая должен быть на отдельной строке.