ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1101. Robot in the Field

Time limit: 1.0 second
Memory limit: 64 MB
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.

Input

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.

Output

You should print robot's route to output, every pair of coordinates in separate line.

Sample

inputoutput
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
Problem Author: Pavel Atnashev
Problem Source: Tetrahedron Team Contest May 2001