Background: The problem setter has run out of ideas for a background story.

This is an interactive problem.

Little Z has found a very old game console with a very simple game on it:

There is a maze, which can be viewed as a grid of $n$ rows and $m$ columns. Some adjacent cells are connected, while others are separated by walls.

To make the game more interesting, the maze satisfies the property that there is exactly one simple path (a path that does not visit any cell more than once) between any two cells. To ensure variety, all mazes are generated randomly. The specific generation method is as follows: list all possible walls, shuffle them randomly, and then consider each wall in order. If adding the wall does not violate the connectivity property of the maze, add it. It can be shown that this process always generates a valid maze.

Little Z needs to control a character to move from $(1,1)$ to $(n,m)$. The console has four directional buttons: up, down, left, and right. When Little Z presses a directional button, the character attempts to move one cell in that direction. If there is a wall in that direction, the move fails; otherwise, the move succeeds.

A level consists of the character starting at $(1,1)$, and Little Z pressing directional buttons until the character reaches $(n,m)$.

Little Z wants to beat the game, but unfortunately, the console's screen is broken. Therefore, Little Z cannot see the state of the maze (the positions of the walls or the current position of the character). Little Z can only determine the size of the maze by the boundaries of the screen.

Fortunately, in this game, the console provides different vibrations after each button press depending on whether the move was successful. Little Z hopes to use this information to clear the game. However, because the console is old and in disrepair, there is a delay in this vibration. Specifically, there exists a non-negative integer $d$ such that the result of the $i$-th operation is fed back after the $(i+d)$-th operation (i.e., before the $(i+d+1)$-th operation, you can know whether the $i$-th operation was successful). Through some trials, Little Z already knows the value of $d$.

Little Z still wants to beat the game, but he also has to write problem statements, so he can only perform at most $t$ operations in each level. Therefore, you need to write a program to simulate Little Z's operations and help him clear the game before the deadline.

There may be multiple levels in the game, so you may need to solve the problem multiple times.

Interaction

You need to include the header file maze.h.

You need to implement the following two functions:

void init(int n,int m,int d,int t);

This function is used for initialization before each test case. Calling this function also indicates that the interaction for the previous test case has ended.

int move(int is);

This function is used to perform the movement. The input variable is the result of the previous feedback, and you need to return the direction of the current operation.

Specifically, suppose this is the $x$-th call to move. If $x \leq d+1$, there is no feedback, and the input $is = -1$. Otherwise, if the $(x-d-1)$-th move operation was successful, the input $is = 1$; if it was unsuccessful, the input $is = 0$.

You need to return an integer between $[0,3]$ representing the direction of movement. $0, 1, 2, 3$ represent up, down, left, and right, respectively. That is, moving from the current position $(x,y)$ to $(x-1,y), (x+1,y), (x,y-1), (x,y+1)$.

The interaction process is as follows:

For each test case, first call init, then call move multiple times. The interactor moves according to the return value of move. This process repeats until the destination is reached or an invalid operation occurs (number of operations exceeds the limit or the return value is invalid), at which point the interaction for that test case ends, and the next test case begins.

You can refer to grader.cpp, maze_sample.cpp, and the sample input files provided in the download package to better understand the interaction process. If you have any further questions, you can ask the problem setter.

You can compile the provided interactor using the following command:

g++ -o grader grader.cpp maze.cpp -O2 -std=c++11

where maze.cpp is your program.

The sample interactor reads input as follows:

First, input a non-negative integer $T$, representing the number of test cases. Then, input each test case sequentially:

First, input four positive integers $n, m, d, t$, the meanings of which are described in the problem statement.

Next, input $2n+1$ lines, each containing a string of length $2m+1$ consisting of o, -, |, and spaces, representing the state of the maze. For the specific input format, you can refer to the provided files. Below is a simple example of an input file:

1
2 4 6 10000
o-o-o-o-o
| |     |
o o o-o o
|   |   |
o-o-o-o-o

After the interaction for each test case ends, the sample interactor will output the number of operations used for that test case. If an invalid operation occurs, the interactor will output the corresponding error message and stop.

If the interaction for all test cases is completed successfully, the interactor will finally output the sum of the number of operations used across all test cases.

The file maze_sample.cpp in the download package is an example of a submission that can pass the first provided test case.

Constraints

Let $T$ be the number of test cases, i.e., the number of times init is called.

For all data, it is guaranteed that $1 \leq n, m \leq 20$ and $0 \leq d \leq 100$. The maze is guaranteed to be generated according to the method described in the problem, and the maze is fixed before the interaction begins.

In the first four subtasks, each subtask contains no more than $4/3/6/6$ test points. You get full marks if you pass all data within a test point; otherwise, you get no points.

The last subtask contains no more than $10$ test points, and the scoring method is as follows:

If there are invalid operations or states such as TLE or RE, the score is $0$. Otherwise, the score is calculated as follows:

For a set of data, let $t_i$ be the number of operations you used. Your final score is: $35 * \min(1, \frac{\max(10^5 - (\sum t_i), 0)}{7 \times 10^4})$

The subtask score is the minimum of the scores of each test point.