Amanojaku and Sequence (Easy Version)

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

const ll MOD = 998244353;
const int MAXF = 1300005; // max m + max n + a little safety

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

vector<ll> fact, ifact;

ll C(int n, int r) {
    if (r < 0 || r > n || n < 0) return 0;
    return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}

int main() {
    setIO();

    fact.assign(MAXF, 1);
    ifact.assign(MAXF, 1);
    for (int i = 1; i < MAXF; i++) fact[i] = fact[i - 1] * i % MOD;
    ifact[MAXF - 1] = modpow(fact[MAXF - 1], MOD - 2);
    for (int i = MAXF - 2; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1) % MOD;

    int TC;
    cin >> TC;
    while (TC--) {
        int n, q;
        cin >> n >> q;

        vector<ll> a(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];

        while (q--) {
            int op, l, r;
            ll m;
            cin >> op >> l >> r >> m;

            ll fixedSum = 0;
            int k = 0;
            for (int i = l; i <= r; i++) {
                if (a[i] == -1) k++;
                else fixedSum += a[i];
            }

            if (fixedSum > m) {
                cout << 0 << '\n';
                continue;
            }

            ll M = m - fixedSum;

            if (k == 0) {
                if (M != 0) {
                    cout << 0 << '\n';
                    continue;
                }

                ll pref = 0, ans = 0;
                for (int i = l; i <= r; i++) {
                    pref = (pref + a[i]) % MOD;
                    ans = (ans + pref * pref) % MOD;
                }
                cout << ans << '\n';
                continue;
            }

            ll N = C((int)(M + k - 1), k - 1);

            ll prefFixed = 0;
            int wildSeen = 0;

            ll A0 = 0; // sum F_i^2
            ll A1 = 0; // sum F_i * t_i
            ll T1 = 0; // sum t_i
            ll T2 = 0; // sum t_i^2

            for (int i = l; i <= r; i++) {
                if (a[i] == -1) {
                    wildSeen++;
                } else {
                    prefFixed += a[i];
                }

                ll F = prefFixed % MOD;
                ll T = wildSeen % MOD;

                A0 = (A0 + F * F) % MOD;
                A1 = (A1 + F * T) % MOD;
                T1 = (T1 + T) % MOD;
                T2 = (T2 + T * T) % MOD;
            }

            ll kMod = k % MOD;
            ll MMod = M % MOD;
            ll invK = modpow(kMod, MOD - 2);
            ll invK2 = invK * invK % MOD;
            ll invK1 = modpow((k + 1) % MOD, MOD - 2);

            ll ans = 0;

            // N * sum F_i^2
            ans = (ans + N * A0) % MOD;

            // 2 * (N * M / k) * sum F_i t_i
            ll linearCoeff = N * MMod % MOD * invK % MOD;
            ans = (ans + 2 * linearCoeff % MOD * A1) % MOD;

            // N * [ M(M+k)/(k^2(k+1)) * sum t_i(k-t_i)
            //       + M^2/k^2 * sum t_i^2 ]
            ll sumTkMinusT2 = (kMod * T1 % MOD - T2 + MOD) % MOD;

            ll coefVar = MMod * ((M + k) % MOD) % MOD;
            coefVar = coefVar * invK2 % MOD * invK1 % MOD;

            ll coefMeanSq = MMod * MMod % MOD * invK2 % MOD;

            ll secondMomentPart = (coefVar * sumTkMinusT2 + coefMeanSq * T2) % MOD;
            ans = (ans + N * secondMomentPart) % MOD;

            cout << ans % MOD << '\n';
        }
    }

    return 0;
}