Problem:
 Score : 500 points    Problem Statement This is an interactive task.  Let N be an odd number at least 3 .  There are N seats arranged in a circle.
The seats are numbered 0 through N-1 .
For each i ( 0 ≤ i ≤ 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 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 N is an odd number at least 3 .  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 ≤ i ≤ N - 1 ). If Seat i is empty, the problem is solved. Otherwise, you are notified of the sex of the person in Seat i .   Guess the ID number of an empty seat by sending at most 20 queries.      Constraints  N is an odd number.  3 ≤ N ≤ 99  999       Input and Output First, N 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, s is Vacant , Male or Female .
Each of these means that Seat i 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 s is Vacant . Otherwise, the verdict is indeterminate.  The verdict is indeterminate if more than 20 queries or ill-formatted queries are sent.        Sample Input / Output 1  In this sample, N = 3 , and Seat 0 , 1 , 2 are occupied by a man, occupied by a woman and vacant, respectively.    Input Output    3  0  Male  1  Female  2  Vacant

Solution (Python):
N = int(input())
L, R = 0, N
D = (L + R) // 2
pin = ["" for _ in range(N)]
print(0)
dp = input()
pin[0] = dp[:]
if dp != "Vacant":
    print(D)
    F = 0
    for i in range(18):
        s = input()
        pin[D] = s[:]
        if s == "Vacant":
            break
        else:
            if (L - D) % 2 == 0 and pin[D%N] != pin[L%N]:
                R = D
                D = (L + R) // 2
            elif (L - D) % 2 == 0 and pin[D%N] == pin[L%N]:
                L = D
                D = (L + R) // 2
            elif (R - D) % 2 == 0 and pin[D%N] != pin[R%N]:
                L = D
                D = (L + R) // 2
            elif (R - D) % 2 == 0 and pin[D%N] == pin[R%N]:
                R = D
                D = (L + R) // 2
            elif (L - D) % 2 == 1 and pin[D%N] == pin[L%N]:
                R = D
                D = (L + R) // 2
            elif (L - D) % 2 == 1 and pin[D%N] != pin[L%N]:
                L = D
                D = (L + R) // 2
            elif (R - D) % 2 == 1 and pin[D%N] == pin[R%N]:
                L = D
                D = (L + R) // 2
            elif (R - D) % 2 == 1 and pin[D%N] != pin[R%N]:
                R = D
                D = (L + R) // 2
            print(D)

Solution (Python):
n = int(input())
q = lambda i:input('%d\n'%i)
i, j = 0, n - 1
a, b = q(i), q(j)
while True:
  k = (j - i + 1) // 2 + i
  c = q(k)
  if (k - i)%2 == (a==c):
    j = k
  else:
    a = c
    i = k

Solution (Python):
N=int(input())
print(0)
s=input()
if s=='Vacant':
  exit()
x=s
print(N-1)
s=input()
if s=='Vacant':
  exit()
left=0
right=N
while True:
  n=(left+right)//2
  print(n)
  s=input()
  if s=='Vacant':
    exit()
  if n%2!=0:
    if s==x:
      right=n
    else:
      left=n
  else:
    if s!=x:
      right=n
    else:
      left=n

Solution (Python):
import sys
N=int(input())
print(0)
s=input()
a=s
if s=='Vacant':
  sys.exit()
left=0
right=N
while True:
  n=(left+right)//2
  print(n)
  s=input()
  if s=='Vacant':
    sys.exit()
  if n%2!=0:
    if s==a:
      right=n
    else:
      left=n
  else:
    if s!=a:
      right=n
    else:
      left=n

Solution (Python):
import sys
N = int(input())
print(0)
s = input()
x = s
if s=='Vacant':
  sys.exit()
l = 0
r = N
while True:
  p = (l+r)//2
  print(p)
  s = input()
  if s=='Vacant':
    sys.exit()
  if p%2==0:
    if s==x:
      l = p
    else:
      r = p
  else:
    if s==x:
      r = p
    else:
      l = p

Solution (Python):
n=int(input())
def ceil(a,b):
    ret = -(-a//b)
    if ret%2==0:
        return ret
    else:
        return ret+1

print(0)
first=input()
if first=="Vacant":
    exit()

l=0
r=n

while abs(l-r)>5:
    nxt = ceil(l+r,2)
    print(nxt)
    ans=input()
    if ans=="Vacant":
        exit()
    if ans==first:
        l=nxt
    else:
        r=nxt


for i in range(l,r):
    print(i)
    ans=input()
    if ans=="Vacant":
        exit()

Solution (Python):
import sys

N = int(input())
seats = [None] * (N + 1)


def main():
    print(0)
    answer = input()
    if answer == "Vacant":
        return
    seats[0] = answer == "Male"
    l, r = 0, N
    while r - l > 1:
        
        assert seats[l] is not None
        q = (l + r) // 2
        
        print(q)
        answer = input()
        if answer == "Vacant":
            return
        seats[q] = answer == "Male"
        if ((q - l) % 2 == 0) ^ (seats[l] == seats[q]):
            r = q
        else:
            l = q
    raise ValueError("something went wrong")


if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
print(0,flush=True)
s=input()
if s=="Vacant":
    exit()
cap=0
if s=="Female":
    cap=1
lo=0
hi=N
while(1):
    mid=(lo+hi)//2
    print(mid,flush=True)
    s=input()
    if s=="Vacant":
        exit()
    gen=0
    if s=="Female":
        gen=1
    if (cap+mid)%2==gen:
        lo=mid
    else:
        hi=mid

Solution (Python):
n = int(input())
li = [0 for i in range(n)]

def call(num):
    print(num,flush=True)

def responce(num):
    res = input()
    if res == "Vacant":
        exit()
    elif res == "Male":
        li[num] = 1
    else:
        li[num] = 2
    
call(0)
responce(0)
call(n-1)
responce(n-1)
l = 0
r = n-1
while True:
    m = (r+l)//2
    call(m)
    responce(m)
    if ((m-l+1)%2 == 1 and li[m] != li[l]) or ((m-l+1)%2 == 0 and li[m] == li[l]):
        r = m
    else:
        l = m

Solution (Python):

n = int(input())

top    = n
bottom = 0
print(0)
s = input()
sex = [-1]*(n+1)
if s == 'Vacant':
    exit(0)
elif s == 'Male':
    sex[0] = sex[n] = 0
else:
    sex[0] = sex[n] = 1

while top - bottom > 1:
    mid = (top+bottom)//2
    print(mid)
    s = input()
    if s  == 'Vacant':
        exit(0)
    elif s == 'Male':
        sex[mid] = 0
    else:
        sex[mid] = 1
    if (sex[top]^sex[mid]) ^ ((top - mid)%2):
        bottom = mid
    else:
        top = mid

print(bottom)
s = input()
if s != 'Vacant':
    print(top%n)
    s = input()

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = int(input())
print(0)
l = input()
r = l
if l == "Vacant":
    exit()

ng,ok = 0,n
while True:
    mid = (ng + ok) // 2
    print(mid)
    q = input()
    if q == "Vacant":
        exit()
    if (q == l) ^ ((mid - ng)%2 == 1):
        ng = mid
        l = q
    else:
        ok = mid
        r = q

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
print(0)
sys.stdout.flush()
s = input()[: -1]
if s == "Vacant":
  exit(0)
zero = s

ok = 0
ng = N
while ng - ok > 1:
  m = (ok + ng) // 2
  print(m)
  sys.stdout.flush()
  s = input()[: -1]
  if s == "Vacant": exit(0)
  if ((m % 2) and (s != zero)) or ((m % 2 == 0) and (s == zero)): ok = m
  else: ng = m
print(ng)
sys.stdout.flush()
exit(0)

Solution (Python):
n=int(input())
l=0
r=n
print(0)
l_color=input()[0]
for i in range(19):
	ans=(r-l)//2+l
	print(ans)
	x=input()[0]
	if x=="V":
		exit()
	elif (x==l_color and (ans-l)%2==1) or (x!=l_color and (ans-l)%2==0):
		r=ans
	else:
		l=ans
		l_color=x

Solution (Python):
N = int(input())

print(0)
start_ans = input()
if start_ans == 'Vacant':
    quit()
end_ans = start_ans
start = 0
end = N
while True:
    mid = (start+end)//2
    print(mid)
    mid_ans = input()
    if mid_ans == 'Vacant':
        quit()
    if (mid-start)%2 == (start_ans == mid_ans):
        end = mid
        end_ans = mid_ans
    else:
        start = mid
        start_ans = mid_ans

Solution (Python):
import sys

def judge(x):
    print(x)
    sys.stdout.flush()
    ans = str(input())
    if ans == "0":
        exit()
    else:
        return ans



n = int(input())
left = 0
mid = n//2
right = n-1

l = judge(left)
m = judge(mid)
r = judge(right)

while True:
    if ((mid-left)%2 == 0 and l == m) or ((mid-right)%2 == 1 and r == m) or ((left-mid)%2 == 1 and l != m) or ((mid-right)% 2 == 0 and r != m):
        left = mid
        mid = (left + right)//2
        l = m
        m = judge(mid)
    else:
        right = mid
        mid = (left + right)//2
        r = m
        m = judge(mid)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())


def q(i):
    print(i)
    r = input()[0]
    if r == 'V':
        exit()
    return r


z = q(0)


def is_ok(k):
    s = q(k)
    if k % 2:
        return z != s
    else:
        return z == s


ok = 0
ng = n
while ng - ok > 1:
    m = (ok + ng) // 2
    if is_ok(m):
        ok = m
    else:
        ng = m

Solution (Python):
N = int(input())

print(0)
s = input()
if s == 'Vacant':
  quit()

root = 0
num = N - 1 
while True:
  n = num // 2
  print((root + n)%N)
  _s = input()
  if _s == 'Vacant':
    quit()
  if (s==_s and n%2==0) or (s!=_s and n%2==1):
    root += n
    s = _s
    num = n + (n%2==1)
  else:
    num = n - 1 + (n%2==0)

Solution (Python):
N = int(input())

print(0, flush=True)
s = input()
if s == 'Vacant':
  quit()

root = 0
num = N - 1 
while True:
  n = num // 2
  print((root + n)%N, flush=True)
  _s = input()
  if _s == 'Vacant':
    quit()
  if (s==_s and n%2==0) or (s!=_s and n%2==1):
    root += n
    s = _s
    num = n + (n%2==1)
  else:
    num = n - 1 + (n%2==0)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    A = 'Vacant'
    N = int(input())

    print(0)
    S = input()
    if S == A:
        return

    r = N
    l = 0
    while l < r - 1:
        m = (r + l) // 2
        print(m)
        s = input()
        if s == A:
            return

        if (m - l) % 2 == 0 and S == s:
            l = m
            S = s
        elif (m - l) % 2 == 1 and S != s:
            l = m
            S = s
        else:
            r = m
    print(l)
    input()


def main():
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())

lst = [-1] * N

r = 0
print (r)
s = str(input())
if s == 'Vacant':
    exit()
elif s == 'Male':
    lst[r] = 1
else:
    lst[r] = 0

l = N - 1

print (l)
s = str(input())
if s == 'Vacant':
    exit()
elif s == 'Male':
    lst[l] = 1
else:
    lst[l] = 0



while True:
    mid = (l + r) // 2
    print (mid)
    s = str(input())
    if s == 'Vacant':
        exit()
    elif s == 'Male':
        lst[mid] = 1
    else:
        lst[mid] = 0

    if (mid - r) % 2 == 0: 
        if lst[r] == lst[mid]: 
            r = mid
        else:
            l = mid
    else: 
        if lst[r] == lst[mid]: 
            l = mid
        else:
            r = mid

Solution (Python):







N=int(input())

print(0,flush = True)
point0 = input()

if point0 == "Vacant":
  exit(0)

print(N-1,flush = True)
if input() == "Vacant":
  exit(0)
  
left = 0
right = N-1
while True:
  mid = abs(left + right) // 2
  print(mid,flush = True)
  val = input()
  if val == "Vacant":
    exit(0)
  if (mid%2 == 0 and point0 == val) or (mid%2 == 1 and point0 != val):
    left = mid
  else:
    right = mid

Solution (Python):
N = r = int(input())
l = 0
print(0)
S = input()
if S == "Vacant":
    exit()
while l < r - 1:
    m = (l + r) // 2
    print(m)
    s = input()
    if s == "Vacant":
        exit()
    if l & 1 == m & 1 and S == s or l & 1 != m & 1 and S != s:
        l = m
        S = s
    else:
        r = m
print(l)
input()
exit()

Solution (Python):
n = int(input())
print(0,flush=True)

prev = input()
if prev=='Vacant': exit()
zero = prev
now=[]

def isok(ans, odd_diff):
    print(ans,flush=True)
    now = input()

    if now == 'Vacant': exit()

    if (now==zero and odd_diff)or(now!=zero and not odd_diff):
        return True
    else:
        return False

ok = n-1 
ng = 0 

while ok - ng > 1:
    m = (ok+ng)//2
    odd_diff = (m%2==1)
    if isok(m, odd_diff):
        ok = m
    else:
        ng = m

print(ok,flush=True)
exit()

Solution (Python):
import sys
import math

def get_seat():
    i = input()
    if i == "Vacant":
        sys.exit()
    return i

n = int(input())
print(0)
seat0 = get_seat()

def check_half(s, e):
    half_i = math.floor((e - s) / 2) + s
    if s == e:
        return
    if (s + 1) >= e:
        print(half_i)
        get_seat()
        return
    print(half_i)
    seat = get_seat()
    correct = False
    if (half_i % 2) == 0:
        correct = seat0 == seat
    else:
        correct = seat0 != seat
    if correct:
        
        check_half(half_i + 1, e)
        check_half(s, half_i)
    else:
        
        check_half(s, half_i)

check_half(1, n)

Solution (Python):
N = int(input())



print(0)
S_0 = input() 

start = -1
goal= N
m = (start+ goal) //2



while True:
    print(m)
    q = (input())
    if q == "Vacant":
        exit(0)

    if m %2 == 0: 
        if q == S_0:
            start = m
        else:
            goal = m
    else:
        if q == S_0:
            goal = m
        else:
            start = m
    m = (start+ goal) //2

Solution (Python):
n=int(input())
print(0)
s=input()
if s=="Vacant":
    exit()
print(n-1)
t=input()
if t=="Vacant":
    exit()
l,r=0,n
for i in range(18):
    mid=(l+r)//2
    print(mid)
    m=input()
    if m=="Vacant":
        exit()
    if (mid-l)%2:
        if s==m:
            r=mid
            t=m
        else:
            l=mid
            s=m
    else:
        if s==m:
            l=mid
            s=m
        else:
            r=mid
            t=m

Solution (Python):
import sys
N = int(input())
print(0, flush=True)
cond = input()
if cond == 'Vacant':
    sys.exit()

l = 0
r = N-1
while r-l > 3:
    mid = (l+r)//2
    if mid % 2 == 1:
        mid += 1

    print(mid, flush=True)
    I = input()
    if I == 'Vacant':
        sys.exit()
    else:
        if cond == I:
            l = mid
        else:
            r = mid

for i in range(l,r+1):
    print(i, flush=True)
    if input() == 'Vacant':
        sys.exit()

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n = int(input())
    a = [-1] * n
    print(0,flush = True)
    s = input()
    if s == 'Vacant':
        return
    elif s == 'Male':
        a[0] = 0
    else:
        a[0] = 1
    
    l = 0
    r = n
    for _ in range(19):
        mid = (r + l)//2
        print(mid,flush = True)
        s = input()
        if s == 'Vacant':
            return
        elif s == 'Male':
            a[mid] = 0
            if a[l] == 0:
                if (mid - l)%2 == 0:
                    l = mid
                else:
                    r = mid
            else:
                if (mid - l)%2 == 1:
                    l = mid
                else:
                    r = mid
        else:
            a[mid] = 1
            if a[l] == 0:
                if (mid - l)%2 == 1:
                    l = mid
                else:
                    r = mid
            else:
                if (mid - l)%2 == 0:
                    l = mid
                else:
                    r = mid
            
    return

if __name__ =='__main__':
    main()

Solution (Python):
n=int(input())

print(0)
zero=input()
if zero=="Vacant":exit()

left,right=0,n
while left<right:
    mid=(left+right)//2
    print(mid)
    ans=input()
    if ans=="Vacant":exit()

    if (ans==zero and mid%2==1) or (ans!=zero and mid%2==0):right=mid+1
    else:left=mid

Solution (Python):


N=int(input())

print(N-1)
if input()=="Vacant":
    exit()
print(0)
who=input()
if who=="Male":
    start=0
elif who=="Female":
    start=1
else:
    exit()

high=N-1
low=0
while True:
    mid=(high+low)//2
    print(mid)
    who=input()
    if who=="Male":
        temp=0
    elif who=="Female":
        temp=1
    else:
        exit()
    
    if (mid%2)^start==temp:
        low=mid
    else:
        high=mid

Solution (Python):
"""
二部探索的なのをやるのな
"""
N = int(input())
sex = {"Male":0, "Female":1}
print(0)
s = input()
init = sex[s]

"""
0 1 2 3 4 5 0
F M   M     F

"""

def f(x):
    print(x)
    s = input()
    ind = sex[s]
    
    if x%2 == (ind+init)%2:
        return False
    else:
        return True 

r = N
l = 0
while r - l > 1:
    mid  = (r + l) // 2
    if f(mid):
        r = mid
    else:
        l = mid

Solution (Python):

















N = int(input())

V = 'Vacant'
F = 'Female'
M = 'Male'
print(0, flush=True)
first = input()
if first == V:
    exit()




left = 0
right = N - 1


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    com = input()
    should_same = (mid - left) % 2 == 0  
    if should_same:
        cond = first == com
    else:
        cond = first != com

    if com == V:
        exit()
    if not cond:  
        
        right = mid - 1
    else:
        
        first = F if com != F else M
        left = mid + 1

Solution (Python):
import bisect
import heapq
import sys
import queue


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    N = int(input())

    left = 0
    right = N - 1
    D = {}
    c = 0
    for _ in range(21):
        if left not in D:
            print(left)
            sys.stdout.flush()
            res = input()
            c += 1
            if res == "Vacant" or c >= 20:
                return

            D[left] = res

        LD = D[left]
        m = (left + right) // 2

        if m not in D:
            print(m)
            sys.stdout.flush()
            res = input()
            c += 1
            if res == "Vacant" and c >= 20:
                return

            D[m] = res

        MD = D[m]

        if (m % 2 == left % 2 and MD == LD) or (m % 2 != left % 2 and MD != LD):
            left = m if left != m else m + 1
        else:
            right = m


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n = II()
    print(0)
    sys.stdout.flush()
    s = S()
    if s == "Vacant":
        return
    x = s
    ok = 0
    ng = n
    while 1:
        mid = (ok + ng) // 2
        print(mid)
        sys.stdout.flush()
        s = S()
        if s == "Vacant":
            return
        if mid & 1 == ok & 1:
            if s == x:
                ok = mid
            else:
                ng = mid
        else:
            if s == x:
                ng = mid
            else:
                ok = mid
                x = s

    return



if __name__ == '__main__':
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n = II()
    print(0,flush = True)
    s = S()
    if s == "Vacant":
        return
    x = s
    ok = 0
    ng = n
    while 1:
        mid = (ok + ng) // 2
        print(mid, flush=True)
        s = S()
        if s == "Vacant":
            return
        if mid & 1 == ok & 1:
            if s == x:
                ok = mid
            else:
                ng = mid
        else:
            if s == x:
                ng = mid
            else:
                ok = mid
                x = s

    return



if __name__ == '__main__':
    solve()

Solution (Python):
N = int(input())
def q(i):
    print(i)
    r = input()[0]
    if r=='V':
        exit()
    return r

z = q(0)
def is_ok(k):
    s = q(k)
    if k%2:
        return z!=s
    else:
        return z==s
ok = 0
ng = N
while ng-ok > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m

Solution (Python):
N= int(input())


def query1(i):
  print(i)
  tmp = input()
  if tmp[0] == 'V':
    exit()
  return tmp


z = query1(0)
  

def judge1(m):
  s = query1(m)
  if m % 2 == 0: 
    return z==s
  else:
    return z!=s
  

l = 0
r = N 
while r - l > 1:
  m = (l + r) // 2
  if judge1(m):
    
    l = m
  else:
    r = m

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())

def query(x):
  print(x)
  sys.stdout.flush()
  re = input()
  return 0 if re == "Male" else 1 if re == "Female" else -1

def clear_checker(a):
  if a == -1: exit()

rq = query(n-1)
clear_checker(rq)
lq = query(0)
clear_checker(lq)

l,r = 0,n-1

while True:
  mid = (l+r)//2
  midq = query(mid)
  clear_checker(midq)
  if ((mid-l) % 2 == 1 and lq == midq) or ((mid-l) % 2 == 0 and lq != midq):
    r,rq = mid,midq
  else:
    l,lq = mid,midq

Solution (Python):
n = int(input())

l = 0
r = n-1

print(l)
seet = input()
if seet == 'Vacant':
    exit(0)

for _ in range(19):
    q = (l+r)//2

    
    
    if l == q:
        print(l+1)
        exit(0)

    print(q)
    tmp = input()
    if ((q-l) & 1 == 0 and tmp == seet) or ((q-l) & 1 == 1 and tmp != seet):
        l = q
        seet = tmp
    else:
        r = q-1

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        elif mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
sys.stdout.flush()
start=input()
if start=='Vacant':exit()
bin(start)

Solution (Python):
import sys
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        elif mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
start=input()
sys.stdout.flush()
if start=='Vacant':exit()
bin(start)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l, flush=True)
ltmp = STR()
if ltmp == 'Vacant':
    exit()
print(r, flush=True)
rtmp = STR()
if rtmp == 'Vacant':
    exit()
for i in range(2, 20):
    c = (l + r) // 2
    print(c, flush=True)
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c
            ltmp = tmp
        else:
            r = c
    else:
        if tmp == ltmp:
            r = c
        else:
            l = c
            ltmp = tmp

Solution (Python):
n=int(input())

def q(i):
    print(i)
    r=input()
    if r=='Vacant':exit()
    return r

t=q(0)

def is_ok(x):
    s=q(x)
    if x%2:
        return t!=s
    else:
        return t==s

ok=0
ng=n

while ng-ok:
    mid=(ok+ng)//2
    if is_ok(mid):
        ok=mid
    else:
        ng=mid

Solution (Python):
n = int(input())
print(0)
l = input()
if l == "Vacant":
    exit()
print(n-1)
r = input()
if r == "Vacant":
    exit()
s = "none"
l_n = 0
r_n = n-1
while True:
    s_n = (l_n+r_n)//2
    print(s_n)
    diff = s_n - l_n
    s = input()
    if s == "Vacant":
        exit()
    elif s == "Male" and diff % 2 == 0:
        if l == "Male":
            l_n = s_n
        else:
            r = "Male"
            r_n = s_n
    elif s == "Male" and diff % 2 == 1:
        if l == "Male":
            r = "Male"
            r_n = s_n
        else:
            l = "Male"
            l_n = s_n
    elif s == "Female" and diff % 2 == 0:
        if l == "Female":
            l_n = s_n
        else:
            r = "Female"
            r_n = s_n
    elif s == "Female" and diff % 2 == 1:
        if l == "Female":
            r = "Female"
            r_n = s_n
        else:
            l = "Female"
            l_n = s_n

Solution (Python):
n = int(input())

def q(x):
    print(x)
    s = str(input())
    if s == 'Vacant':
        exit()
    else:
        return s

y = q(0)
q(n-1)

def ok(x):
    if x%2 == 0:
        if y == q(x):
            return False
        else:
            return True
    else:
        if y != q(x):
            return False
        else:
            return True

l = 0
r = n-1
while l+1 < r:
    c =(l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(r)

Solution (Python):
N=int(input())

l = 0
r = N-1
print(l)
t = input()
if t=='Vacant': exit()
for i in range(20-1):
    q = (l+r)//2
    if l==q:
        print(l+1)
        exit()
    print(q)
    s = input()
    if s=='Vacant': exit()
    if ((q-l)&1==0 and s==t) or ((q-l)&1==1 and s!=t):
        l=q
        t=s
    else:
        r=q-1

Solution (Python):
N = int(input())

def read(i):
    print(i, flush=True)
    s = input()
    if s == 'Vacant':
        exit()
    return s

s = read(0)
isMale = 0 if s == 'Male' else 1
s = read(N - 1)

A = [i % 2 == isMale for i in range(N)]

ok = 0
ng = N
while ng - ok > 1:
    mid = (ok + ng) // 2
    s = read(mid)

    isMale = s == 'Male'

    if isMale == A[mid]:
        ok = mid
    else:
        ng = mid

read(ng)
read(ok)
exit()

Solution (Python):
N = int(input())

def q(i):
    print(i)
    r = input()[0]
    if r=='V':
        exit()
    return r

z = q(0)
def is_ok(k):
    s = q(k)
    if k%2:
        return z!=s
    else:
        return z==s
ok = 0
ng = N
while ng-ok > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m

Solution (Python):
N = int(input())

print(0)
left = input().rstrip("\n")
if left == "Vacant":
    exit()
print(N - 1)
right = input().rstrip("\n")
if right == "Vacant":
    exit()

even = left
odd = "Female" if even == "Male" else "Male"

left = 0
right = N - 1
while right - left > 1:
    mid = (right + left) // 2
    print(mid)
    s = input().rstrip("\n")
    if s == "Vacant":
        exit()
    
    if mid % 2 == 0:
        if even == s: 
            left = mid + 1
        else: 
            right = mid - 1
    else:
        if odd == s: 
            left = mid + 1
        else: 
            right = mid - 1

print(left)
s = input().rstrip("\n")
if s == "Vacant":
    exit()
print(right)
s = input().rstrip("\n")
if s == "Vacant":
    exit()