题目描述

本题是一道 交互题。

评测系统事先想好了一个整数 $x$，满足 $1 \le x \le 10^9$。你需要通过若干次询问把它猜出来。

每次询问，你输出一个整数 $m$（保证 $1 \le m \le 10^9$）；评测系统会回答一个字符：

回答	含义
>	$x > m$，答案比你猜的大
<	$x < m$，答案比你猜的小
=	$x = m$，你猜中了

收到 = 之后，你的程序应当 立即结束。

你最多可以询问 50 次。询问次数超出限制，或程序结束时仍未猜中，本题不得分。

交互格式

每次询问输出一行一个整数 $m$，然后读取一行一个字符作为回答。

一个合法的交互过程示例（设 $x = 625$）：

500
>
750
<
625
=

输入格式

本题没有常规意义上的初始输入 —— 你的程序一启动就可以直接开始询问。

每次询问输出之后，从标准输入读入一行一个字符作为回答（>、< 或 =）。

输出格式

每次询问输出一行一个整数，代表你的猜测。输出后必须 刷新输出缓冲区，否则评测系统收不到你的询问，会导致 Idleness limit exceeded / 超时。

• C++：使用 cout << m << endl;（endl 会自动刷新），或先 cout << m << "\n"; 再 cout.flush();
• C：printf("%lld\n", m); fflush(stdout);
• Python：print(m) 之后必须 sys.stdout.flush()

另外，猜中之后请让程序 正常结束（C/C++ 里就是走到 return 0;）。 以非零状态码退出会被评测机判为运行时错误 —— 哪怕你已经猜对了。

数据范围与约定

• $1 \le x \le 10^9$
• 询问次数上限：$50$
• 每次询问必须满足 $1 \le m \le 10^9$，否则判 Wrong Answer

提示

1. 交互题和普通题最大的区别：普通题是把所有输入一次读完再算；交互题是"问一句、收一句、再问一句"，你必须在每次输出后刷新缓冲区，否则两边会互相等待，程序永远卡死。
2. 每次询问最多只能把可能性砍掉一半，所以答案数量为 $10^9$ 时，$\lceil \log_2 10^9 \rceil = 30$ 次询问就足够了 —— 上限给到 50 次是留了余量的。
3. 注意二分查找的边界写法，以及 mid = (lo + hi) / 2 在 lo + hi 较大时的溢出问题。

样例交互过程

一个完整的交互过程如下（左边是你程序的输出，右边是评测系统的回答）。设隐藏答案 $x = 340$：

你的程序输出	评测系统的回答	含义
500	<	猜大了，答案比 500 小
250	>	猜小了，答案比 250 大
375	<	猜大了
312	>	猜小了
343	<	猜大了
327	>	猜小了
335
339
341	<	猜大了
340	=	猜中，程序结束

共询问 10 次。真写程序时，你不需要像上面这样"人肉"二分 —— 交给循环就行。