题目背景

Cirno 有一个区间 $[a,b](1\le a \le b \le n)$，而你的任务是在规定的次数内帮 Rumia 猜出这个区间。

每次，你可向 Cirno 询问一个数字 $k$，而 Cirno 会告诉你这个数字与区间 $[a,b]$ 的关系。

题目描述

为了猜到这个区间，你需要实现一个函数 std::pair<int,int> Guess(int n,int c)，这个函数的作用是在不超过 $c$ 次询问中猜对 $[1,n]$ 中的一个子闭区间 $[a,b]$，返回值为你最终确定的区间，以 std::pair<int,int> 的形式返回。

你可以调用交互库中一个叫做 Query 的函数，其原型为 int Query(int x)，返回值为：

• 若 $x < a$，返回 $-1$。
• 若 $x \in [a,b]$，返回 $0$。
• 若 $x > b$，返回 $1$。

你调用 Query 函数的次数不超过 $c$ 才能得到这个点的分数，否则这个点为 $0$ 分。有关该函数的调用请参考「说明/提示」部分。

在一个测试点中，你的 Guess 函数可能被调用多次，最多不超过 $5000$ 次。为了保证你的程序不会超时，你需要额外实现一个函数 void init()，这个函数只会在开始时被交互库调用一次。当然，它的实现可以为空。

由于 Rumia 的编译器只支持 C++，所以你只能使用 C++ 语言（包括 C++，C++11，C++14，C++17）来解决本题。

输入格式

样例中输入四个数字 $n$，$a$，$b$，$c$。这些数字你无法读取。

输出格式

样例中给输出三个数字 $l$，$r$，$q$。分别表示你猜的区间与 Query 调用测次数。这些你不用输出。

5 2 3 5

2 3 0

提示

样例解释

需要求的区间是 $[2,3]$，区间左右端点可能的范围是 $[1,5]$，你最多猜 $5$ 次。

数据范围与约定

对于所有数据保证 $1 \le a \le b \le n$；除 SubtaskExtra 外，保证 $1\le n\le1500$。

子任务

Subtask1（$10$ points）：$c=n$。

Subtask2（$30$ points）：$c=30$。

Subtask3（$30$ points）：$c=22$。

Subtask4（$30$ points）：$c=20$。

附加任务

SubtaskExtra（$1$ point）：$1\le n\le 10^6$，$c=\lfloor\log_2 n\rfloor+\lfloor\log_2 \frac{4n}{3}\rfloor$。

本题使用 Special Judge，$100$ 与 $101$ 分均视作 Accepted.

提示

如果你不知道怎么解决交互题，可以参考这题。

本题模板程序与模板交互库见附件中的 SampleProgram.cpp 与 SampleInteractor.cpp。