For each query \((A,B,C,D)\), the answer is

\[ \begin{aligned} &\sum_{A\le x\le B} \sum_{C\le y\le D} [2\mid x+y]((x-1)M+y) \\&=\left(\sum_{A\le x\le B}(x-1)M\sum_{C\le y\le D} [2\mid x+y]\right)+\left(\sum_{C\le y\le D}y\sum_{A\le x\le B} [2\mid x+y]\right). \end{aligned} \]

For \(i\in \{0,1\}\), let \(f_i(l,r)\) be the number of integers \(x\) such that \(x\in [l,r]\) and \(x\equiv i\pmod 2\), and \(s_i(l,r)\) be the sum of such integers. It’s easy to calculate one \(f_i(l,r)\) or one \(s_i(l,r)\) in \(O(1)\) time.

Consider the parity of \(x,y\) in the above formula. Thus, the answer is

\[ \sum_{i=0}^1 M(s_i(A,B)-f_i(A,B))f_i(C,D)+s_i(C,D)f_i(A,B). \]

The total time complexity is \(O(Q)\).