2020 年 “联想杯”全国高校程序设计在线邀请赛暨第三届上海理工大学程序设计竞赛热身赛

D. 猜价格

单点时限: 1.0 sec

内存限制: 512 MB

你女朋友最近叒不理你了。这一定是因为你双十一没有给她买东西。异地恋实在是太辛苦了,浦西到浦东的距离,对于你来说,就像是上海到多伦多的距离。

曾有诗这样写道:

世上最遥远的距离,不是生与死的距离,不是天各一方,而是我就站在你面前,你却不知道我爱你。

因此你决定参加某猜价格小游戏,猜对了就可以获得送女朋友的礼物了。但是这个游戏比普通的猜价格更加困难一些,因为可能会传递给你错误信息。

给定一个 $1$ 到 $2^n-1$ 之间的价格。你要把它猜出来。

每次只会回答是 >, < 还是 =,分别表示你猜的价格是太大了,还是太小了,还是猜中了。

另外,在任意连续 $k$ 次回答中,会有恰好一次是「反话」。他会把 > 说成 <,把 < 说成 >。但是 = 还是 =

你只有 $2n$ 次机会(包括猜中的那一次)。

交互流程

首先会输入两个整数 $n$ 和 $k$ ($1 \le n \le 60$, $1 \le k \le 10^9$)。

每一次,你都要猜一个 $1$ 到 $2^n-1$ 之间的数。然后 oxx 会回答你 >, < 或者 =。如果回答是 =,你的程序应该立即退出。

如果你使用了超过 $2n$ 次机会,你会得到 Wrong answer;如果你输出了不合法的内容,会得到 Runtime errorWrong answer;运行时间超限会导致 Time limit exceeded 或者 Idleness limit exceeded

注意,在每次输出后要清空缓冲区。

样例

Input
2 4
1

3

2
Output
<

<

=

提示

样例中猜测的范围是 $[1,3]$。连续 4 次中必有 1 次是假的。

第一次猜 1,偏小,回答 <

第二次猜 3,偏大,但是假了,回答 <

第三次猜 2,猜中了。