题目背景：出题人已经不会写背景了。

这是一道交互题。

小 Z 找到了一个年代非常久远的游戏机，这个游戏机上有一个非常简单的游戏：

有一个迷宫，它可以看成由 $n$ 行 $m$ 列的方格组成。一些相邻的格子间可以双向通行，但还有一些相邻的格子间被墙阻隔。

为了增加一点游戏的趣味性，这个迷宫满足任意两个方格之间，正好有一条简单路径（不经过重复方格）。为了保证游戏的多样性，所有的迷宫都使用随机方式生成。具体的生成方式为，将所有可能的墙排成一列，然后随机打乱，接下来按顺序考虑所有墙，如果加入这堵墙后迷宫仍然连通就加入这堵墙。可以发现这样一定能生成一个合法的迷宫。

小 Z 需要操控一个人物从 $(1,1)$ 走到 $(n,m)$，游戏机有四个方向按键，对应上下左右。小 Z 按下一个方向键时，人物会向对应方向走一个格子。如果这个方向上是墙，则这次移动失败，否则这次移动成功。

游戏中一关的过程为，初始人物在 $(1,1)$，小 Z 可以任意按方向键，人物到达 $(n,m)$ 时就通过了这一关。

小 Z 想要通关这个游戏，但很不幸的是，游戏机的屏幕坏了，因此小 Z 看不到迷宫中的状态（墙的位置以及当前人物的位置），小 Z 只能通过屏幕边界判断迷宫的大小。

幸运的是，这个游戏中，每次按下方向键后游戏机会根据这次移动是否成功发出不同的震动，因此小 Z 希望用这个信息来通过游戏。但因为年久游戏机失修，这个震动存在延迟。具体来说，存在一个非负整数 $d$，第 $i$ 次操作的结果会在第 $i+d$ 次操作后反馈（即在第 $i+d+1$ 次操作之前，你可以知道第 $i$ 次操作对应的移动是否成功）。通过一些尝试，小 Z 已经知道了 $d$ 的值。

小 Z 还是想要通过这个游戏，但他还要去写题面，因此他只能在每一关中进行不超过 $t$ 次操作。因此你需要写一个程序，模拟小 Z 的操作过程，并帮助小 Z 在ddl之前通关。

游戏可能存在多个关卡，因此你可能需要解决多次问题。

交互方式

你需要包含头文件 maze.h。

你需要实现如下两个函数：

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

这个函数用来进行每组数据前的初始化操作。调用这个函数也表示上一组数据的交互过程已经结束。

int move(int is);

这个函数用来进行移动的过程，传入变量为上次反馈的结果，你需要返回这次操作移动的方向。

具体来说，设这是第 $x$ 次调用 move，如果 $x\leq d+1$，则不存在反馈，传入的 $is=-1$。否则，如果第 $x-d-1$ 次移动操作是成功的，则传入的 $is=1$，如果移动不成功则传入的 $is=0$。

你需要返回一个 $[0,3]$ 间的整数，表示移动的方向。$0,1,2,3$ 分别表示向上，向下，向左，向右。即从当前位置 $(x,y)$ 分别移动到 $(x-1,y),(x+1,y),(x,y-1),(x,y+1)$。

交互过程为：

对于每组数据，首先调用一次 init，接下来多次调用 move，交互库按照 move 的返回值进行移动，重复这一过程直到到达终点或者出现不合法的操作（次数超过限制或者返回值不合法）后结束这组数据的交互过程，随后开始下一组数据的交互。

你可以参考下发文件中的 grader.cpp，maze_sample.cpp 以及样例输入文件以更好地理解交互过程。如果还有疑问可以提问出题人

你可以使用如下方式编译下发交互库：

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

其中 maze.cpp 是你的程序。

样例交互库使用如下方式读入：

首先输入一个非负整数 $T$，表示数据组数。接下来依次输入每一组数据：

首先输入一行四个正整数 $n,m,d,t$，含义见题面。

接下来输入 $2n+1$ 行，每行一个长度为 $2m+1$，包含 o，-，| 以及空格的字符串，表示迷宫的状态。具体输入格式可以参考下发文件，以下是一个简单的输入文件例子：

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

在每组数据的交互过程结束后，样例交互库会输出这组数据使用的操作次数。如果出现不合法操作，交互库会输出对应错误信息并停止。

如果成功地完成了每一组数据的交互，则最后交互库会输出所有数据中使用的操作次数之和。

下发文件中的 maze_sample.cpp 是一个提交程序的示例，它可以通过第一组下发数据。

数据范围与限制

设 $T$ 为数据组数，即调用 init 的次数。

对于所有数据，保证 $1\leq n,m\leq 20,0\leq d\leq 100$，保证迷宫按照题目描述中给出的方式生成，且迷宫在交互开始前已经确定。

前四个子任务中，每个子任务包含不超过 $4/3/6/6$ 个测试点。如果你通过了一个测试点内的所有数据则获得满分，否则不得分。

最后一个子任务包含不超过 $10$ 个测试点，计分方式如下：

如果存在不合法的操作或者出现 TLE，RE 等状态，则分数为 $0$ 分。否则按照如下方式计算分数：

对于一组数据，记你使用的操作次数为 $t_i$。则你最后的得分为：$35*\min(1,\frac{\max(10^5-(\sum t_i),0)}{7\times 10^4})$

子任务得分取每个测试点得分的最小值。