Robot

A factory workshop is shaped like a rectangle, measuring M by N meters, where 1 ≤ M, N ≤ 30. Engineer Petro has designed a robot that can navigate the workshop to perform useful tasks. The robot moves on tiles that are each 1 by 1 meter, covering the workshop floor, and can only move parallel to the coordinate axes.

The robot is equipped with 4 state registers: A, B, C, and D. Each register can hold a value of either TRUE or FALSE. Some tiles in the workshop have radio triggers that change the state of certain registers. Additionally, other tiles may have radio beacons that, based on the truth of a formula associated with the beacon, cause the robot to turn 90 degrees left or right. If the formula is true, the robot turns right.

Special services have taken an interest in Petro's robot and want to test its performance in extreme conditions, such as radiation, underwater, in volcanic craters, on other planets, and more. For these tests, all equipment was removed from the workshop, and a number of radio beacons and triggers were placed. The robot starts from a specified empty tile X_0, Y_0 with an initial direction A_0 (0, 90, 180, or 270 degrees, measured clockwise from the upward direction). Initially, all the robot's registers are set to FALSE.

The robot's battery allows it to make K (0 < K ≤ 10^9) moves to adjacent tiles before stopping. There is also a risk that Petro might have incorrectly placed the triggers and beacons, causing the robot to crash into the workshop wall at some point. Your task is to determine whether the robot will complete the tests successfully and, if so, identify the tile where it will stop.

The coordinate axes originate from the top-left corner, point (1,1), extending to the right and downward. M is the workshop's horizontal size, and N is its vertical size. The number of triggers, P, does not exceed 10000, and the number of radio beacons, Q, does not exceed 25.

Input

The first line of the input file contains 8 numbers: M, N, P, Q, K, X_0, Y_0, A_0. Following this, there are P lines detailing the triggers in the format "X Y R", where R is the register name. Then, there are Q lines describing the radio beacons in the format "X Y F", where F is a boolean function of variables A..D, with a maximum length of 250 characters. This function is expressed as a valid formula, where:

• A, B, C, D, TRUE, FALSE are valid formulas.

• If F is a valid formula, then "(F)" and "NOT F" are also valid formulas.

• If F and G are valid formulas, then "F AND G", "F OR G", and "F XOR G" are valid formulas. The NOT operation has the highest priority, while other operations have equal priority and are evaluated from left to right. For example, A AND NOT B OR C XOR D is equivalent to (((A AND (NOT B)) OR C) XOR D).

• Letter case does not matter.

• A valid formula does not contain unnecessary spaces.

Output

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

Examples

Note

In the illustration, the robot moves in a "figure eight" pattern with a total length of 42 meters. Therefore, moving 42n+1 meters is equivalent to moving 1 meter, so the robot will stop on the tile with coordinates "3 5".