题目描述

これはインタラクティブな問題です。

$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 & Output Format

最初に、$N$ が次の形式で標準入力から与えられる。

$N$

次に、クエリを繰り返し送る。 クエリは次の形式で標準出力へ出力する。 行末には改行を出力せよ。

$i$

これに対するクエリの答えは、次の形式で標準入力から与えられる。

$s$

$s$ は Vacant, Male, Female のどれかである。 これらはそれぞれ、席 $i$ の状態が「空席」「男性が座っている」「女性が座っている」であることを表す。

题目大意

这是一道交互题。

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

提示

制約

• $N$ は奇数である。
• $3\ <\ =\ N\ <\ =\ 99,999$

注意

• 出力の度に標準出力を flush せよ。 そうしない場合、TLE の可能性がある。
• $s$ が Vacant の場合、すぐにプログラムを終了せよ。 そうしない場合、ジャッジ結果は不定である。
• クエリ回数が $20$ を超えた場合、およびクエリの形式が正しくない場合、ジャッジ結果は不定である。

入出力例 1

このサンプルでは、$N\ =\ 3$ であり、席 $0$, $1$, $2$ の状態はそれぞれ「男性が座っている」「女性が座っている」「空席」である。

InputOutput30Male1Female2Vacant