Vacant Seat

**这是一道交互题。** N为3以上的奇数。 有N个座位围成一圈，座位由0到N-1编号，对于每一个座位i(0<=i<=N-2)，座位i和i+1是相邻的。座位n-1和0是相邻的。每个座位要么空着，要么坐着男人或女人。没有两个相邻的座位被性别相同的人坐着。可以证明在N为大于3的奇数时至少有一个空位。 给定N，你需要找出一个空位。每次可以询问一个座位i(0<=i<=N-1)的状态，若这个位置是空的，则你通过了这个测试点，否则将会返回位置上人的性别。你要在20次询问内找出一个空座位。 N为奇数，3<=N<=99999

[problemUrl]: https://atcoder.jp/contests/apc001/tasks/apc001_c **これはインタラクティブな問題です。** $ N $ を $ 3 $ 以上の奇数とします。 $ N $ 個の席が円状に並んでいます。 席には $ 0 $ から $ N\ -\ 1 $ まで番号が振られています。 各 $ i $ ($ 0\ <\ =\ i\ <\ =\ N\ -\ 2 $) について、席 $ i $ と席 $ i\ +\ 1 $ は隣り合っています。 また、席 $ N\ -\ 1 $ と席 $ 0 $ は隣り合っています。 各席の状態は「空席」「男性が座っている」「女性が座っている」のどれかです。 ただし、同性どうしが隣り合う席に座っていることはありません。 $ N $ が $ 3 $ 以上の奇数の場合、空席が少なくとも $ 1 $ つは存在することが示せます。 あなたには $ N $ のみが与えられ、各席の状態は与えられません。 あなたの目標は、どれか $ 1 $ つの空席の番号を当てることです。 そのために、あなたは次のクエリを繰り返し送ることができます。 - 整数 $ i $ ($ 0\ <\ =\ i\ <\ =\ N\ -\ 1 $) を選ぶ。 席 $ i $ が空席ならば、正答となる。 そうでなければ、席 $ i $ に座っている人の性別が知らされる。 クエリを高々 $ 20 $ 回まで送ることで、どれか $ 1 $ つの空席の番号を当ててください。 ### Input &amp; Output Format 最初に、$ N $ が次の形式で標準入力から与えられる。 > $ N $ 次に、クエリを繰り返し送る。 クエリは次の形式で標準出力へ出力する。 行末には改行を出力せよ。 > $ i $ これに対するクエリの答えは、次の形式で標準入力から与えられる。 > $ s $ $ s $ は `Vacant`, `Male`, `Female` のどれかである。 これらはそれぞれ、席 $ i $ の状態が「空席」「男性が座っている」「女性が座っている」であることを表す。

### 制約 - $ N $ は奇数である。 - $ 3\ <\ =\ N\ <\ =\ 99,999 $ ### 注意 - 出力の度に標準出力を flush せよ。 そうしない場合、`TLE` の可能性がある。 - $ s $ が `Vacant` の場合、すぐにプログラムを終了せよ。 そうしない場合、ジャッジ結果は不定である。 - クエリ回数が $ 20 $ を超えた場合、およびクエリの形式が正しくない場合、ジャッジ結果は不定である。 ### 入出力例 1 このサンプルでは、$ N\ =\ 3 $ であり、席 $ 0 $, $ 1 $, $ 2 $ の状態はそれぞれ「男性が座っている」「女性が座っている」「空席」である。 InputOutput30Male1Female2Vacant