Задача №383. Робот

Некоторый заводской цех представляет собой прямоугольник размером M на N метров (1 <= M, N <= 30). Инженер-конструктор Петя создал робота, который может перемещаться по территории цеха и выполнять некоторую общественно-полезную работу. Робот может перемещаться только по плитам, размером 1 на 1 метр, которыми выложен пол цеха, и только параллельно осям координат. У робота есть 4 регистра состояния, A, B, C и D. Каждый регистр может принимать одно из двух значений - TRUE или FALSE. На некоторых плитах цеха стоят радио-триггеры, которые переключают состояние каких-то регистров робота. Также на некоторых других плитах могут находиться радиомаяки, которые в зависимости от истинности формулы, соответствующей данному маяку, заставляют робота повернуть на 90 градусов налево или направо. В случае истинности совершается поворот направо. Спецслужбы заинтересовались разработкой Пети, и решили проверить пригодность робота для работ в условиях радиации, под водой, в кратерах вулканов, на других планетах и много где еще. Для испытаний из цеха было вынесено все оборудование, поставлено некоторое количество радиомаяков и триггеров. Начиная с некоторой пустой плиты X0, Y0 под начальным углом A0 (0, 90, 180 или 270 градусов, отсчитывая от направления вверх по часовой стрелке) был запущен робот. Изначально состояния всех регистров робота - FALSE. Аккумуляторных батарей робота хватит на K (0 < K <= 10^9) перемещений на соседнюю плиту. После этого он остановится. Кроме того, возможен такой вариант, что Петя неправильно расставил триггеры и маяки, поэтому на некотором шаге робот врежется в стену цеха. Необходимо определить, уцелеет ли робот после испытаний и на какой клетке он остановится в случае положительного ответа на первый вопрос. Оси координат направлены из левого верхнего угла - точки (1, 1) - соответственно вправо и вниз. M - размер цеха по горизонтали, а N - по вертикали. Количество триггеров - P - не превосходит 10000, а радиомаяков - Q - 25.

Формат входного файла:

На первой строке входного файла записаны 8 чисел - M, N, P, Q, K, X0, Y0, A0. Далее на Р строках записаны триггеры в формате "X Y R", где R - название регистра. Далее на Q строках записаны радиомаяки в формате "X Y F", где F - булева функция от переменных A..D длиной не более 250 символов, заданная корректной формулой, причем:

1) A, B, C, D, TRUE, FALSE - корректные формулы
2) Если F - корректная формула, то "(F)" и "NOT F" - корректные формулы
3) Если F и G - корректные формулы, то "F AND G", "F OR G" и "F XOR G" - корректные формулы
4) Операция NOT имеет наивысший приоритет, остальные операции имеют одинаковые приоритеты и выполняются слева направо, т.е. A AND NOT B OR C XOR D эквивалентно (((A AND (NOT B)) OR C) XOR D)
5) Регистр букв не имеет значения
6) Корректная формула не содержит лишних пробелов

Формат выходного файла:

В случае успешного исхода вывести координаты плиты, где остановится робот. В случае краха эксперимента вывести в выходной файл единственное число "-1".

Примеры:

Входной файл	Выходной файл
8 8 1 9 420000001 3 4 180 3 3 A 3 5 FALSE 6 5 FALSE 6 2 FALSE 3 2 A 3 1 FALSE 1 1 FALSE 1 8 FALSE 2 8 FALSE 2 2 TRUE	3 5
*Комментарий* В соответствии с рисунком, робот будет двигаться по "восьмерке" суммарной длиной 42 метра. Следовательно, прохождение 42n+1 метра эквивалентно прохождению 1 метра, т.е. робот остановится на плите с координатами (3, 5).

Сдать: для сдачи задач необходимо войти в систему