Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
print(0, flush=True)

for i in [0, n - 1]:
    res = input()
    if res == "Vacant":
        exit()


left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
print(0, flush=True)

for i in [0, n - 1]:
    res = input()
    if res == "Vacant":
        exit()


left = 0
right = n - 1
gen = res


while abs(right - left) > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()
    
    if res == "Vacant":
        exit()
    
    if (right - mid) % 2 == 0:
        if gen == res:
            right = mid
        else:
            left = mid
    else:
        if gen != res:
            right = mid
        else:
            left = mid

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Buggy python submission (verdict: Time Limit Exceeded):
def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    while abs(ok - ng) >= 2:
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            ok = mid
        else:
            ng = mid
    return (ok + ng) // 2


n = int(input())
gen = is_ok(n - 1)
ret = meguru_bisect_kai(0, n - 1, gen)
is_ok(ret)

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Buggy python submission (verdict: Time Limit Exceeded):
def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            ok = mid
        else:
            ng = mid
    return ok


n = int(input())
gen = is_ok(n - 1)
ret = meguru_bisect_kai(0, n - 1, gen)
is_ok(ret)

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    cnt = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            ok = mid
        else:
            ng = mid
    return ok


n = int(input())
gen = is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    cnt = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            ok = mid
        else:
            ng = mid
        cnt += 1
    return ok


n = int(input())
gen = is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    cnt = 0
    while (abs(ok - ng) > 1) and cnt <= 20:
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            if (ok - mid) % 2 == 1:
                if gen == "Male":
                    gen = "Famale"
                else:
                    gen = "Male"
            ok = mid
        else:
            ng = mid
        cnt += 1
    return ok


n = int(input())
gen = is_ok(0)
is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    cnt = 0
    while (abs(ok - ng) > 1) and cnt <= 20:
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            if (ok - mid) % 2 == 0:
                if gen == "Male":
                    gen = "Famale"
                else:
                    gen = "Male"
            ok = mid
        else:
            ng = mid
        cnt += 1
    return ok


n = int(input())
gen = is_ok(0)
is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            if (ok - mid) % 2 == 0:
                if gen == "Male":
                    gen = "Famale"
                else:
                    gen = "Male"
            ok = mid
        else:
            ng = mid
    return ok


n = int(input())
gen = is_ok(0)
is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            ok = mid
        else:
            ng = mid
            if gen == "Male":
                gen = "Female"
            else:
                gen = "Male"
    return ok


n = int(input())
gen = is_ok(0)
is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Buggy python submission (verdict: Time Limit Exceeded):
def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            ok = mid
        else:
            ng = mid
            if gen == "Male":
                gen = "Female"
            else:
                gen = "Male"
    return ok


n = int(input())
gen = is_ok(0)
is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid

Buggy python submission (verdict: Time Limit Exceeded):
def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            ok = mid
        else:
            ng = mid
            if gen == "Male":
                gen = "Female"
            else:
                gen = "Male"
    return ok


n = int(input())
gen = is_ok(0)
is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

Fixed submission:
n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid