题目描述

这是一个交互式任务。

设 $N$ 是一个至少为 $3$ 的奇数。

有 $N$ 个座位围成一圈。座位以 $0$ 到 $N-1$ 进行编号。对于每个 $i$（$0 ≤ i ≤ N - 2$），座位 $i$ 和座位 $i + 1$ 是相邻的。此外，座位 $N - 1$ 和座位 $0$ 也是相邻的。

每个座位要么是空置的，要么被男性或女性占据。然而，相邻的两个座位不能被相同性别的两个人占据。当 $N$ 是一个至少为 $3$ 的奇数时，可以证明至少有一个空座位。

给定 $N$，但座位的状态未知。你的目标是正确猜测出任意一个空座位的编号。为了做到这一点，你可以重复发送以下查询：

• 选择一个整数 $i$（$0 ≤ i ≤ N - 1$）。如果座位 $i$ 是空置的，则问题解决。否则，你会被告知座位 $i$ 上人的性别。

通过发送最多 $20$ 个查询来猜测一个空座位的编号。

约束条件

• $N$ 是一个奇数。
• $3 ≤ N ≤ 99\,999$

输入输出格式

首先，从标准输入中以以下格式给出 $N$：

$N$

然后，你应该发送查询。一个查询应该以以下格式打印到标准输出。在末尾打印一个换行符。

$i$

对查询的回答从标准输入以以下格式给出：

$s$

这里，$s$ 是 Vacant、Male 或 Female。其中每个值分别表示座位 $i$ 是空置的、被男性占据的或被女性占据的。

注意事项

• 每次打印内容时，请刷新标准输出。否则，可能导致超时错误。
• 当 $s$ 是 Vacant 时，立即终止程序。否则，判定结果是不确定的。
• 如果发送了超过 $20$ 个查询或者查询格式不正确，则判定结果是不确定的。

示例输入/输出 1

在这个示例中，$N = 3$，座位 $0$、$1$、$2$ 分别被男性占据、女性占据和为空。

输入

输出

3

0

Male

1

Female

2

Vacant