\(A_i,B_i,C_i,D_i\) が与えられる質問の答えを、以下 \(f(A_i,B_i,C_i,D_i)\) と書きます。また、\(A>B\) もしくは \(C>D\) のとき \(f(A,B,C,D)=0\) とします。

対称性に着目した別解を紹介します。

\(B-A\) と \(D-C\) の偶奇が一致している場合、\(f(A,B,C,D)\) を簡単に求められます。

対称性から正整数が書かれたマスの値の平均が \((\frac{A+B}{2}-1)\times M + \frac{C+D}{2}\) と求まります。正整数が書かれたマスの個数を数えるのも容易なので、\(f(A,B,C,D)\) を求められました。

\(B-A\) と \(D-C\) の偶奇が異なる場合を考えます。

\(D-C\) が奇数の場合、恒等式

\[f(A,B,C,D)=f(A,B,C,D-1)+f(A,B,D,D)\]

を用います。

恒等式の右辺の \(f\) ではどちらも \(B-A,D-C\) の偶奇が一致しているので、右辺は先述の方法で求められます。よって \(f(A,B,C,D)\) も求まります。

\(D-C\) が偶数の場合、恒等式

\[f(A,B,C,D)=f(A,B-1,C,D)+f(B,B,C,D)\]

を用いると同様の手法で計算できます。

実装例(c++):

#include <bits/stdc++.h>

#include <atcoder/modint>

using namespace std;
using mint = atcoder::modint998244353;
using ll = long long;

int n, m;
mint f(int a, int b, int c, int d) {
    if(a > b or c > d) return 0;
    if(((b - a) ^ (d - c)) & 1) {
        if((d - c) & 1)
            return f(a, b, c, d - 1) + f(a, b, d, d);
        else
            return f(a, b - 1, c, d) + f(b, b, c, d);
    }
    mint ave = (mint(a + b) / 2 - 1) * m + mint(c + d) / 2;
    mint cnt = (ll)(b - a + 1) * (d - c + 1) / 2;
    if(!((b - a) & 1) and !((a + c) & 1)) cnt++;
    return ave * cnt;
}

int main() {
    cin >> n >> m;
    int q;
    cin >> q;
    while(q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << f(a, b, c, d).val() << endl;
    }
}