ゲームの皇帝和に関する問題です。

\(N\) 個の不偏ゲーム \(G_1,G_2,\ldots,G_N\) の皇帝和 とは、各手番で \(N\) 個のゲームのうち \(1\) つに \(1\) 回以上連続して着手し、他の \(N-1\) 個のゲームそれぞれに対し \(0\) 回以上 \(1\) 回以下着手するゲームと定義されます。

本問題であれば、\(G_i\) は最初 \(A_i\) 個の石があり、各手番では石を\(1\) 個以上 \(B_i\) 個以下取り除くゲームと定義した時の \(N\) 個の皇帝和として得られるゲームの勝敗判定ができれば良いです。

そして、皇帝和の勝敗判定は以下のように行うことができます：

• 後手必勝盤面 \(G\) に対し、\(l(G)\) を以下のように定義する：
  • \(G\) から \(1\) 回以上着手して到達可能な後手必勝盤面 \(G'\) 全てに対する \(l(G')+1\) の最大値、ただし到達可能な後手必勝盤面が存在しない場合は \(0\) とする。
• このとき、\(G_1,G_2,\ldots,G_N\) が全て後手必勝盤面かつ \(l(G_1),l(G_2),\dots,l(G_N)\) の総 \(\mathrm{XOR}\) が \(0\) である場合後手必勝、そうでない場合先手必勝である。

石が \(A\) 個あり、\(1\) 回の着手で石を \(1\) 個以上 \(B\) 個以下取れるゲームを考えると、後手必勝である条件は \(A\bmod (B+1)=0\) であるため \(\displaystyle l(G)=\frac{A}{B+1}\) となります。したがって、全ての \(i\) に対して \(A_i\bmod (B_i+1)=0\) であり、\(\displaystyle \frac{A_i}{B_i+1}\) の総 \(\mathrm{XOR}\) が \(0\) であれば後手必勝、そうでないならば先手必勝と判定することができます。