eolymp
bolt
Try our new interface for solving problems

Robot

Time limit 1 second
Memory limit 64 MiB

Некоторый заводской цех представляет собой прямоугольник размером M на N метров (1 ≤ M, N ≤ 30). Инженер-конструктор Петя создал робота, который может перемещаться по территории цеха и выполнять некоторую общественно-полезную работу. Робот может перемещаться только по плитам, размером 1 на 1 метр, которыми выложен пол цеха, и только параллельно осям координат.

У робота есть 4 регистра состояния, A,B, C и D. Каждый регистр может принимать одно из двух значений - TRUE или FALSE. На некоторых плитах цеха стоят радио-триггеры, которые переключают состояние каких-то регистров робота. Также на некоторых других плитах могут находиться радиомаяки, которые в зависимости от истинности формулы, соответствующей данному маяку, заставляют робота повернуть на 90 градусов налево или направо. В случае истинности совершается поворот направо.

Спецслужбы заинтересовались разработкой Пети, и решили проверить пригодность робота для работ в условиях радиации, под водой, в кратерах вулканов, на других планетах и много где еще. Для испытаний из цеха было вынесено все оборудование, поставлено некоторое количество радиомаяков и триггеров. Начиная с некоторой пустой плиты X_0, Y_0 под начальным углом A_0 (0,90,180 или 270 градусов, отсчитывая от направления вверх по часовой стрелке) был запущен робот. Изначально состояния всех регистров робота - FALSE.

Аккумуляторных батарей робота хватит на K (0 < K ≤ 10^9) перемещений на соседнюю плиту. После этого он остановится. Кроме того, возможен такой вариант, что Петя неправильно расставил триггеры и маяки, поэтому на некотором шаге робот врежется в стену цеха. Необходимо определить, уцелеет ли робот после испытаний и на какой клетке он остановится в случае положительного ответа на первый вопрос.

Оси координат направлены из левого верхнего угла - точки (1,1) - соответственно вправо и вниз. M - размер цеха по горизонтали, а N - по вертикали. Количество триггеров - P- не превосходит 10000, а радиомаяков - Q - 25.

Input data

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

  • A, B, C, D, TRUE, FALSE – корректные формулы

  • Если F – корректная формула, то "(F)" и "NOT F" – корректные формулы

  • Если F и G – корректные формулы, то "F AND G", "F OR G" и "F XOR G" – корректные формулы. Операция NOT имеет наивысший приоритет, остальные операции имеют одинаковые приоритеты и выполняются слева направо, т.е. A AND NOT B OR C XOR D эквивалентно (((A AND (NOT B)) OR C) XOR D)

  • регистр букв не имеет значения

  • корректная формула не содержит лишних пробелов.

Output data

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

Комментарий

В соответствии с рисунком, робот будет двигаться по "восьмерке" суммарной длиной 42 метра. Следовательно, прохождение 42n+1 метра эквивалентно прохождению 1 метра, т.е. робот остановится на плите с координатами "3 5".

Examples

Input example #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
Output example #1
3 5