[user:nihal2001,2021-03-05] posted a [blog](https://mirror.codeforces.com/blog/entry/88374) for asking the following question:↵
↵
There are $n$ stones, two players take turn to choose $x$ stones, such that $1 \leq x \leq n$ and $x \And n = 0$. The one who cannot make choose lose.↵
↵
Determine who is the winner, The first one or the second?↵
↵
I [proved](https://mirror.codeforces.com/blog/entry/88374?#comment-767851) that If $n$ belongs to https://oeis.org/A295897, the second player win(can be solved in $O(\log n)$). ↵
↵
My Question(Multiple piles version of above question):↵
↵
There are $n_1, \cdots, n_m$ stones, two players take turn to choose an index $i$ and $x_i$ stones, such that $1 \leq i \leq m$, $1 \leq x_i \leq n_i$ and $x_i \And n_i = 0$. The one who cannot make choose lose.↵
↵
Who will be the winner?↵
↵
This turn out to compute Sprague-Grundy function for $n_1 \cdots, n_m$. The first player win if and only if $sg(n_1) \wedge \cdots \wedge sg(n_m) \neq 0$↵
↵
I know how to compute $sg(n)$ in $O(n^2 \log n)$, but I can't give it a formula or compute efficiently like $O(\log n)$ or $O(\log^2 n)$↵
↵
Thanks in advance.↵
↵
**UPD**: $O(n^{log_2 3} \log n)$ [implement](https://paste.ubuntu.com/p/cMFbnZtBDs/) based on [user:wery0,2021-03-08]'s comment.
↵
There are $n$ stones, two players take turn to choose $x$ stones, such that $1 \leq x \leq n$ and $x \And n = 0$. The one who cannot make choose lose.↵
↵
Determine who is the winner, The first one or the second?↵
↵
I [proved](https://mirror.codeforces.com/blog/entry/88374?#comment-767851) that If $n$ belongs to https://oeis.org/A295897, the second player win(can be solved in $O(\log n)$). ↵
↵
My Question(Multiple piles version of above question):↵
↵
There are $n_1, \cdots, n_m$ stones, two players take turn to choose an index $i$ and $x_i$ stones, such that $1 \leq i \leq m$, $1 \leq x_i \leq n_i$ and $x_i \And n_i = 0$. The one who cannot make choose lose.↵
↵
Who will be the winner?↵
↵
This turn out to compute Sprague-Grundy function for $n_1 \cdots, n_m$. The first player win if and only if $sg(n_1) \wedge \cdots \wedge sg(n_m) \neq 0$↵
↵
I know how to compute $sg(n)$ in $O(n^2 \log n)$, but I can't give it a formula or compute efficiently like $O(\log n)$ or $O(\log^2 n)$↵
↵
Thanks in advance.↵
↵
**UPD**: $O(n^{log_2 3} \log n)$ [implement](https://paste.ubuntu.com/p/cMFbnZtBDs/) based on [user:wery0,2021-03-08]'s comment.
