exception Exodus

let rec solve i j b b' =
  let k = (i + j) / 2 in
  Printf.printf "%d\n" k;
  let b'' =
    match read_line () with
    | "Male" -> true
    | "Female" -> false
    | "Vacant" -> raise Exodus in
  if (k - i) mod 2 = 0 <> (b = b'') then solve i k b b''
  else if (j - k) mod 2 = 0 <> (b'' = b') then solve k j b'' b'
  else (i, k, j, b, b'', b'')

let rec solve_acc candidates =
  List.map (fun (i, j, b, b') -> solve i j b b') candidates
  |> List.map (fun (i, j, k, b, b', b'') -> [(i, j, b, b'); (j, k, b', b'')])
  |> List.concat 
  |> solve_acc

let () =
  let n = int_of_string @@ read_line () in
  print_endline "0";
  try
    begin match read_line () with
    | "Male" -> true
    | "Female" -> false
    | "Vacant" -> raise Exodus
    end
    |> (fun b -> solve_acc [(0, n, b, b)])
  with Exodus -> ()