Робот
Деякий заводський цех являє собой прямокутник розміром 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".
Приклади
Примітка
У відповідності з рисунком, робот буде рухатись по "вісімці" сумарною довжиною 42 метри. Відповідно, проходженння 42n+1 метра еквівалентно проходженню 1 метра, тобто робот зупиниться на плиті з координатами "3 5".