19269번 - Vacant Seat 다국어인터랙티브

문제

Let $N \ge 3$ be an odd number.

There are $N$ seats arranged in a circle. The seats are numbered 0ドル$ through $N-1$. For each $i$ (0ドル \le i \le N - 2$), seat $i$ and seat $i + 1$ are adjacent. Also, seat $N - 1$ and seat 0ドル$ are adjacent.

Each seat is either vacant, or occupied by a man or a woman. However, no two adjacent seats are occupied by two people of the same sex. It can be shown that there is at least one empty seat because $N$ is an odd number greater than 1ドル$.

You are given $N,ドル but the states of the seats are not given. Your objective is to correctly guess the ID number of any one of the empty seats. To do so, you can repeatedly send the following query:

Choose an integer $i$ (0ドル \le i \le N - 1$). If Seat $i$ is empty, the problem is solved. Otherwise, you are notified of the sex of the person at seat $i$.

Guess the ID number of an empty seat by sending at most 20ドル$ queries.

입력

출력

제한

프로토콜

In the first line you are given one integer $N$ --- the number of seats ($N$ is odd, 3ドル \le N \le 99,999円$).

After that, you start to send queries. A query consists of one integer $i$ (0ドル \le i \le N-1$) --- number of seat. Do not forget to end the query by end-of-line character and to flush standard output after each query.

The responce of the interactor is one of three possible answers: "Vacant", "Male" and "Female". Each of these means that Seat $i$ is empty, occupied by a man and occupied by a woman, respectively.

When you receive "Vacant" answer, immediately terminate the program. If you send more than 20 queries, you will receive the Wrong Answer verdict.

힌트

In the sample, $N = 3,ドル and Seat 0ドル,ドル 1ドル,ドル 2ドル$ are occupied by a man, occupied by a woman and vacant, respectively.