**这是一道交互题。** Putata 有 $n$ 盏灯，从左到右分别编号为 $1$ 至 $n$。一开始，所有灯都是关闭的。其中有一盏灯是他最喜欢的，但这盏灯的编号被隐藏了。Budada 想知道 Putata 最喜欢的灯是哪一盏，并且他可以进行以下询问： - 将编号为 $x$ 的灯打开，并向 Putata 询问“她最喜欢的那盏灯左侧被点亮的灯的数量”以及“她最喜欢的那盏灯右侧被点亮的灯的数量”的差值的绝对值。 Budada 只能最多做 $40$ 次询问，请帮助他找出 Putata 最喜欢的那盏灯。

你需要在你的程序中实例化 `Interactive` 类，并通过调用该类的方法进行交互。提交程序后，系统会自动引用实现该类的头文件。你可以在调试你的程序时简单实现该类的方法，但请务必在提交程序时将其移除。 `Interactive` 类提供了三个公共接口： - `int init()` -- 初始化函数。请务必写在你的程序开头调用该函数，该函数将会返回一个 `int` 类型的数值，代指题意中的 $n$. - `int query(int x)` -- 询问函数。调用该函数后，第 $x$ 盏灯将会被点亮，并根据题意返回一个数值。你最多调用这个函数 $40$ 次，否则将会获得 `Wrong Answer`。 - `void submit(int x)` -- 答案提交函数。在你确定答案之后，请调用该函数，并传入你的答案。调用此函数后将会自动结束程序。 样例仅供交互流程参考，并非代指实际输入输出。Special Judge 仅为提示错误信息用。

Adapted from 第二十届浙江省大学生程序设计竞赛