该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

千寻被困在了神隐世界的测试之塔中。塔主告诉她：“我在 $1$ 到 $10⁹$ 之间藏了一个秘密数字。如果你能在不超过 50 次的提问中找出它，就能获得自由。”

每次，千寻可以问塔主一个整数 $x$，塔主会回答：

$0$：恭喜你，猜对了！试炼结束；

$-1$：你的数字太小了；

$1$：你的数字太大了。

千寻需要用最少的提问次数，保证无论塔主选择哪个数字，她都能在 50 次内确定它。 现在，请你帮她编写这个程序。

Format

Input

本题为交互式问题。 程序无需读取初始输入。

Output

在每次询问时，输出一个整数 $x$ 表示当前猜测，并换行、刷新缓冲区。

Samples

没有样例喔！！！

Limitation

1s, 1024KiB for each test case.