题目描述

33DAI 和 Tom 玩一个猜数游戏。Tom 心里想好了一个整数 $x$，满足 $1 \le x \le n$，但 33DAI 不知道 $x$ 是多少。

33DAI 可以向 Tom 提问。每次提问他给出一个整数 $y$，Tom 回答 $x$ 是否严格大于 $y$。33DAI 也可以在任意时刻直接猜出 $x$。

33DAI 一共最多只能进行 $60$ 次操作（一次提问或一次猜测都算一次操作）。请你帮他赢得游戏。

交互规则

本题没有输入文件，你通过与交互器对话来获取信息。你的程序需要从标准输入读入数据、向标准输出写数据。

第一步：从标准输入读入一个整数 $n$（$1 \le n \le 10^9$），表示 $x$ 的取值范围。

接下来的每一次操作，你向标准输出写一行，格式必须是下面两种之一：

• 1 y：提问。其中 $y$ 必须是满足 $0 \le y \le n$ 的整数。交互器会回答一行：
  • yes：表示 $x > y$；
  • no：表示 $x \le y$。
• 2 y：猜数。其中 $y$ 必须是满足 $1 \le y \le n$ 的整数。如果 $y = x$，交互器会输出一行 win，本题该测试点通过；如果 $y \ne x$，本题该测试点判为 Wrong Answer。

每次输出一行后，必须立即刷新输出缓冲区，否则交互器会读到旧数据而判错。C++ 中的做法是：

printf("1 %d\n", y);
fflush(stdout);
// 用 cout 的话写 cout << "1 " << y << endl;（endl 会刷新）或 cout.flush();

限制：提问与猜测的总次数不能超过 $60$ 次，否则判为 Wrong Answer。

样例

下面是一次合法的交互过程（$n = 10$，隐藏的数是 $x = 7$）。空行只是为了排版，实际输出中不要有空行。

交互器        你的程序
10
              1 5
yes
              1 8
no
              1 6
yes
              2 7
win

样例解释

• 交互器给出 $n = 10$；
• 你问 1 5，交互器回答 yes，说明 $x > 5$；
• 你问 1 8，交互器回答 no，说明 $x \le 8$；
• 你问 1 6，交互器回答 yes，说明 $x > 6$；
• 你猜 2 7，正好等于 $x$，交互器回答 win，本测试点通过。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^9$；
• $1 \le x \le n$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。