P7345 【DSOI 2021】吟唱的金色花海

**这是一道 IO 交互题。** 在很久很久以前，有一片开满了白色郁金香的花海。某一天，绽放了一朵金色郁金香，从此，这片花海开始了它永生的吟唱…… > _(Dutch) $\textit{\textcolor{blue}{Het\ universum\ zingt\ voor\ mij!}}$_

在某一时刻，在某处出现了一朵金色郁金香。然后接下来每一秒，每朵金色郁金香会向其上下左右四个点中所有白色郁金香吟唱，使其变为金色郁金香。 现在告诉你一个点 $(x_0,y_0)$，以及它自第一朵金色郁金香出现起，刚变成金色郁金香的那一秒 $t$，你需要找出最初出现的金色郁金香的位置。 每次你可以输出一行 `0 x y`,然后程序会返回一个值 $0$ 或 $1$，$0$ 表示 $(x,y)$ 在第 $t$ 秒是白色郁金香， $1$ 表示 $(x,y)$ 在第 $t$ 秒是金色郁金香。 你可以输出一行 `1 x y` 告知程序最初出现最初出现的金色郁金香的位置为 $(x,y)$ 以结束程序。

**本题有多组数据。**\ 第一行输入一个正整数 $Q$ ,表示有 $Q$ 组数据。\ 对于每组数据，输入四个整数 $t,x_0,y_0,k$ 开始交互。数据用单个空格隔开，代表第 $t$ 秒时位于 $(x_0,y_0)$ 处的郁金香刚变成了金色。你最多可以询问的次数为 $k$。

对于每一组数据，在你确定答案之后，输出一行 `1 x y` 以结束本组数据，代表你判断 $(x,y)$ 是金色郁金香最开始出现的地方。 ### 交互格式 交互过程中，用 `0 x y` 的形式输出一行以执行一次操作。然后你应输入一个布尔值，即操作的返回值 $x$。若 $x=0$ ，表示 $(x,y)$ 在第 $t$ 秒是白色郁金香；若 $x=1$ ，表示 $(x,y)$ 在第 $t$ 秒是金色郁金香。 上述的所有输入都应从**标准输入**中读入，所有输出都应向**标准输出**中输出。输出一行后必须**清空缓冲区** ，否则你的评测有可能被判为**Time Limit Exceeded**。清空缓冲区方式如下： * 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。 * 在 Pascal 中，使用 `flush(output)`。 * 其他语言请自行查阅文档。

| 测试点编号 | $k =$ | $t \le$ | $Q=$ | | :--------: | :------------: | :-----: | :----: | | 1 | $10000$ | $1$ | $100$ | | 2~3 | $10000$ | $5$ | $100$ | | 4~6 | $4t$ | $100$ | $100$ | | 7~10 | $2 \times MAX$ | $100$ | $100$ | | 11~14 | $MAX+1$ | $10^4$ | $5000$ | | 15~20 | $MAX$ | $10^4$ | $5000$ | 每个测试点的分值均为 $5$ 分。 记:在最劣情况下询问 $MAX=\lceil\log_2(t+1)\rceil+2$ 次一定能得出答案。保证 $1 \le t \le 10^4$，$1 \le Q \le 5000$ 且得出的结果的 $x,y$ 的绝对值不大于 $10^5$。 *** 提示：由于交互题的特性，若你的算法错误，评测结果为 **TLE** 属于正常现象，请将鼠标放在测试点上查看你的具体错误原因。具体的： - 若你输出的结果错误，会返回 **You made a mistake in data i!** - 若你询问了过多的次数，会返回 **You ask too many times in data i!**