这是一个交互式问题。

设 $N \ge 3$ 为一个奇数。

有 $N$ 个座位排成一个圆圈。座位编号为 $0$ 到 $N-1$。对于每个 $i$ ($0 \le i \le N-2$)，座位 $i$ 和座位 $i+1$ 相邻。此外，座位 $N-1$ 和座位 $0$ 也相邻。

每个座位要么是空的，要么坐着一名男性或一名女性。然而，没有两个相邻的座位坐着相同性别的人。由于 $N$ 是大于 $1$ 的奇数，可以证明至少有一个空座位。

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

选择一个整数 $i$ ($0 \le i \le N-1$)。如果座位 $i$ 是空的，则问题解决。否则，你将获知座位 $i$ 上的人的性别。

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

交互

首先，你将获得一个整数 $N$ —— 座位的数量（$N$ 为奇数，$3 \le N \le 99\,999$）。

之后，你开始发送查询。查询由一个整数 $i$ ($0 \le i \le N-1$) 组成 —— 座位的编号。不要忘记在查询末尾加上换行符，并在每次查询后刷新标准输出。

交互器的响应是以下三种可能的答案之一：“Vacant”、“Male” 和 “Female”。它们分别表示座位 $i$ 是空的、坐着一名男性以及坐着一名女性。

当你收到 “Vacant” 答案时，请立即终止程序。如果你发送了超过 $20$ 次查询，你将收到 Wrong Answer 判决。

样例

输入格式 1

3
Male
Female
Vacant

输出格式 1

0
1
2

说明

在样例中，$N = 3$，座位 $0, 1, 2$ 分别坐着一名男性、一名女性和空位。