#APC001C. Vacant Seat

Vacant Seat

Score : 500500 points

Problem Statement

This is an interactive task.

Let NN be an odd number at least 33.

There are NN seats arranged in a circle. The seats are numbered 00 through N1N-1. For each ii (0iN20 \leq i \leq N - 2), Seat ii and Seat i+1i + 1 are adjacent. Also, Seat N1N - 1 and Seat 00 are adjacent.

Each seat is either vacant, or oppupied 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 where NN is an odd number at least 33.

You are given NN, 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 ii (0iN10 \leq i \leq N - 1). If Seat ii is empty, the problem is solved. Otherwise, you are notified of the sex of the person in Seat ii.

Guess the ID number of an empty seat by sending at most 2020 queries.

Constraints

  • NN is an odd number.
  • 3N993 \leq N \leq 99 999999

Input and Output

First, NN is given from Standard Input in the following format:

N

Then, you should send queries. A query should be printed to Standart Output in the following format. Print a newline at the end.

i

The response to the query is given from Standard Input in the following format:

s

Here, ss is Vacant, Male or Female. Each of these means that Seat ii is empty, occupied by a man and occupied by a woman, respectively.

Notice

  • Flush Standard Output each time you print something. Failure to do so may result in TLE.
  • Immediately terminate the program when ss is Vacant. Otherwise, the verdict is indeterminate.
  • The verdict is indeterminate if more than 2020 queries or ill-formatted queries are sent.

Sample Input / Output 1

In this sample, N=3N = 3, and Seat 00, 11, 22 are occupied by a man, occupied by a woman and vacant, respectively.

Input Output
3
0
Male
1
Female
2
Vacant