\(k\) を固定した時，\(A_i\) が 答えにどのように寄与するか考えます．

一次元の累積和を複数回取る様子は，二次元のグリッド上で縦横に移動することと対応しています． これより，\(\binom{(N-i)+(k-1)}{k-1}\) が奇数ならば答えに \(A_i\) が XOR され，偶数のときは何も影響しない，とわかります．

\(\binom{(N-i)+(k-1)}{k-1}\) が奇数であるということは，\((N-i)\) と \(k-1\) をそれぞれ \(2\) 進表記したときに，\(1\) が立っている bit の位置がすべて異なるということと同値です．（リュカの定理）

ここで，\(S\) を，\(\max(N,M) \leq S\) を満たす最小の \(2\) 冪の数とします． すると，\(\binom{(N-i)+(k-1)}{k-1}\) が奇数という条件は，\(S-1-(N-i)\) の \(1\) が立っている bit の位置が，\(k-1\) の \(1\) が立っている bit の位置を包含している，と言い換えることができます．

ここまでくれば，あとは高速ゼータ変換の要領で解くことができます． 計算量は \(O(\max(N,M) \log \max(N,M))\) です．

解答例(c++)