There is a field [−N..N]×[−N..N].
At initial moment, robot stands at point (0, 0). It starts moving in (1, 0) direction.
Robot moves according to a program.
Program is a correct boolean expression. It contains operators NOT, AND, OR
(NOT has highest priority, OR - lowest), brackets '(', ')', constants 'TRUE' and 'FALSE',
and registers 'A', ..., 'Z'. Initially, all robot's registers are FALSE. Robot moves forward until it reaches a fork. Then, robot evaluate the expression and turns right if it is TRUE and turns left if it is FALSE. Besides, there are some points in the field, standing on which makes one of robot's registers to invert. You are asked to print robot's route until it falls out of the field.
First line contains boolean expression. The length of expression ≤ 250.
Second line contains three integers 1 ≤ N ≤ 100, 0 ≤ M ≤ 100, 0 ≤ K ≤ 100.
M — number of forks, K — number of register inverting points. Then follows M lines, each of them contains two integers X, Y — coordinates of forks.
Then follows K lines, each of them contains two integers X, Y and character C — coordinates of register inverting point and name of register, which inverts. You may assume, that there is no fork at point (0, 0). You may assume, that no two objects (forks or register inverting points) coincide.
You may assume, that after some moves robot falls out of the field.
You should print robot's route to output, every pair of coordinates in separate line.
NOT((A OR NOT B) AND (A OR B)) OR NOT (A AND NOT B OR TRUE)
1 5 2
0 1 A
-1 0 D
Problem Author: Pavel Atnashev
Problem Source: Tetrahedron Team Contest May 2001