eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Робот

Робот

Ліміт часу 1 секунда
Ліміт використання пам'яті 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.

Вхідні дані

У першому рядку вхідного файлу записано 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)

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

  • коректна формула не містить зайвих пропусків.

Вихідні дані

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

Приклад

Вхідні дані #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
Вихідні дані #1
3 5

Примітка

У відповідності з рисунком, робот буде рухатись по "вісімці" сумарною довжиною 42 метри. Відповідно, проходженння 42n+1 метра еквівалентно проходженню 1 метра, тобто робот зупиниться на плиті з координатами "3 5".