ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1101. Робот в поле

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Задано поле [−N..N]×[−N..N]. В начальный момент робот стоит в точке (0, 0). Он начинает двигаться в направлении (1, 0). Робот двигается в соответствии с программой. Программой является правильное логическое выражение. Она может содержать логические операторы NOT (не), AND (и), OR (или) (у NOT высший приоритет, у OR — низший), скобки '(', ')', константы 'TRUE' и 'FALSE', а также регистры 'A', ..., 'Z'. Изначально все регистры робота содержат FALSE. Робот двигается вперёд до тех пор, пока он не встретит развилку. Затем робот вычисляет выражение и поворачивает направо, если значение этого выражения TRUE, или налево, если значение FALSE. Кроме того, существуют точки на поле, нахождение в которых заставляет какой-то один из регистров инвертироваться (принять противоположное значение). Вас попросили напечатать маршрут робота до тех пор, пока он не выйдет за пределы поля.

Исходные данные

Первая строка содержит логическое выражение. Длина выражения  ≤ 250. Вторая строка содержит три целых числа 1 ≤ N ≤ 100, 0 ≤ M ≤ 100, 0 ≤ K ≤ 100. M — количество развилок, K — количество точек, инвертирующих значение какого-либо регистра. Затем следуют M строк, в каждой по два целых числа X, Y — координаты развилок. Затем следуют K строк, в каждой по два целых числа X, Y, а также символ C — координаты точки инвертирования регистра и имя регистра, который она инвертирует. Можно считать, что в точке (0, 0) нет вилки. Можно считать, что никакие два объекта (вилки или точки инвертирования регистров) не имеют одинаковых координат. Можно считать, что после некоторого количества ходов робот выйдет за пределы поля.

Результат

Вам нужно вывести маршрут робота по одной паре координат в строке.

Пример

исходные данныерезультат
NOT((A OR NOT B) AND (A OR B)) OR NOT (A AND NOT B OR TRUE)
1 5 2
1 0
1 1
1 -1
-1 -1
-1 1
0 1 A
-1 0 D
0 0
1 0
1 -1
0 -1
-1 -1
-1 0
-1 1
0 1
1 1
Автор задачи: Павел Атнашев
Источник задачи: Tetrahedron Team Contest May 2001