For a fixed \(k\), let us consider the contribution of \(A_i\) to the answer.

Repeated applications of one-dimensional prefix sum correspond to vertical and horizontal moves in a two-dimensional grid. It follows that if \(\binom{(N-i)+(k-1)}{k-1}\) is odd, the answer gets XORed by \(A_i\), and if it is even, the answer is unaffected.

\(\binom{(N-i)+(k-1)}{k-1}\) is odd iff the positions of all \(1\)’s in the binary representations of \((N-i)\) and \(k-1\) are different.（Lucas’s theorem）

Now, let \(S\) be the smallest power of \(2\) such that \(\max(N,M) \leq S\). Then, the condition of \(\binom{(N-i)+(k-1)}{k-1}\) being odd can be rephrased into the set of bit positions of \(1\)’s in \(S-1-(N-i)\) containing the set of bit positions of \(1\)’s in \(k-1\).

At this point, we can solve the problem in a way similar to the fast zeta transform. The complexity is \(O(\max(N,M) \log \max(N,M))\).

Sample Submission (C++)