Bonus : あなたはジャッジです。
勝ち局面が回ってきたら必ず勝てる着手を選ぶジャッジシステムを作ってください。

この問題は 前計算 \(\mathrm{O} (N^2)\), (局面がクエリとして与えられたときに)クエリ \(\mathrm{O}(N)\) で解くことができます。

次の事実を利用します。

連続する \(n\) 個の整数のみ存在する状態の Grundy 数を \(g_n\) とする。(ただし \(g_0 = 0\)) このとき、\(L, R\) の値に関わらず

\[g_n \leq n\]

が成り立つ。

(証明) \(i < n\) について \(g_i \leq i\) が成り立つと仮定すると、\(i+j \lt n\) を満たす非負整数 \(i, j\) について

\[g_i \oplus g_j \leq g_i + g_j \leq i + j \lt n\]

が成り立つので、

\[g_n \leq \mathrm{mex}(\lbrace g_i \oplus g_j | i + j < n\rbrace) \leq n\]

です。よって \(g_0 = 0\) と合わせて帰納的に示せます。\(\square\)

この事実を利用すると、詳細は略しますが、あとは変則的な尺取りの要領で前計算を行えば Bonus を \(\mathrm{O} (N^2)\) で解くことができます。(連想配列などのデータ構造を利用せずに実装できるため、定数倍が膨らむ心配もなく安心してジャッジすることができます。)