Robot#759

Robot

1 second

64 megabytes

Hard

A factory workshop is a rectangle measuring $M$ by $N$ meters $(1 \leq M, N \leq 30)$ (1 \leq M, N \leq 30). Engineer Petro has created a robot that is able to move around the workshop and perform useful tasks. The robot moves only on tiles of $1 \times 1$ 1 \times 1 meters that form the floor of the workshop, and can move only parallel to the coordinate axes.

The robot has $4$ state registers: $A$ , $B$ , $C$ , and $D$ . Each register can be either $TRUE$ or $FALSE$ . Some tiles contain radio triggers, which change the state of certain registers. Also, some other tiles may have radio beacons, which make the robot turn $90$ degrees left or right, depending on the truth of a logical formula assigned to the beacon. If the formula evaluates to true, the robot turns right; otherwise, it turns left.

Special services became interested in Petro's robot and decided to test its suitability for work in extreme conditions—such as under radiation, underwater, in volcanic craters, on other planets, and in many other places. For the tests, all the equipment was removed from the workshop, and a certain number of radio beacons and triggers were placed. The robot starts from a certain empty tile $X_{0}, Y_{0}$ X_0, Y_0 and an initial orientation $A_{0}$ A_0 ( $0, 90, 180$ , or $270$ degrees, measured clockwise from up). At the start, all register values are $FALSE$ .

The robot's battery is sufficient for $K$ $(0 < K \leq 1 0^{9})$ (0 < K \leq 10^9) moves to an adjacent tile. After that, it stops. There is also a possibility that Petro may have placed the triggers and beacons incorrectly, so the robot might crash into a workshop wall at some step. You need to determine whether the robot will survive the tests and, if so, on which tile it will stop.

The coordinate axes are directed from the top-left corner—point $(1, 1)$ —to the right and downward. $M$ is the horizontal size of the workshop, $N$ is the vertical size. The number of triggers is $P$ (not more than $10000$ ), and the number of radio beacons is $Q$ (not more than $25$ ).

Input

The first line of the input contains $8$ numbers: $M, N, P, Q, K, X_{0}, Y_{0}, A_{0}$ M, N, P, Q, K, X_0, Y_0, A_0. The next $P$ lines describe the triggers in the format " $X Y R$ ", where $R$ is the register name. The next $Q$ lines describe the radio beacons in the format " $X Y F$ ", where $F$ is a logical function with variables $A .. D$ , with a maximum length of $250$ characters, given as a correct formula, such that:

$A$ , $B$ , $C$ , $D$ , $TRUE$ , $FALSE$ are valid formulas.
If $F$ is a valid formula, " $(F)$ " and "NOT F" are also valid formulas.
If $F$ and $G$ are valid formulas, so are "F AND G", "F OR G", and "F XOR G". The NOT operation has the highest precedence; the other operations have equal precedence and are evaluated left to right—that is, $A AND NOT B OR C XOR D$ A\ \text{AND}\ \text{NOT}\ B\ \text{OR}\ C\ \text{XOR}\ D is equivalent to $(((A AND (NOT B)) OR C) XOR D)$ (((A\ \text{AND}\ (\text{NOT}\ B))\ \text{OR}\ C)\ \text{XOR}\ D).
Register letter case does not matter.
A valid formula contains no extra spaces.

Output

If the robot completes all the tests successfully, output the coordinates of the tile where it stops. If the experiment fails, print a single number "-1".

Examples

Example 1

Note

In the illustration, the robot moves along a "figure eight" with a total length of $42$ meters. Therefore, passing $42 n + 1$ 42n+1 meters is equivalent to passing $1$ meter, so the robot will stop at tile "3 5".