\(A\) の初期値および各操作における \(B_1, B_2, \dots, B_K\) の分の寄与については適切に答えに加算するものとして、以下、各操作における \(B_{K+1}\) 以降の項の分の寄与を高速に計算する方法を考えます。また、\(r_q-l_q+1 \leq K\) である操作については既に処理が終わっているため以下では考えないものとします。

基本的なアイデアとしては、各操作における \(B\) がすべて同じ線形漸化式に従っていることをうまく利用し、答えの \(i\) 項目 \((1 \leq i \leq N)\) に対する各操作の寄与をまとめて計算します。結論としては、以下のアルゴリズムによって答えが求まります。

1. 配列 \(C=(C_1, C_2, \dots, C_N)\) を用意し、すべての要素を \(0\) で初期化する。
2. \(i=K+1,K+2,\dots,N\) の順に以下を行う。
   1. \(l_q = i-K\) を満たす各操作に対して以下を行う。
      • 各 \(j\ (0 \leq j < K)\) について \(C_{i-K+j}\) に \(B_{j+1}\) を足す。
   2. \(r_q = i-1\) を満たす各操作に対して以下を行う。
      • 各 \(j\ (0 \leq j < K)\) について \(C_{i-K+j}\) から \(B_{r_q-l_q-K+2+j}\) を引く（\(B_{r_q-l_q-K+2+j}\) の求め方については後述）。
   3. \(C_i\) を \(P_1C_{i-1}+P_2C_{i-2}+\dots +P_KC_{i-K}\) で更新する。
   4. 答えの \(i\) 項目に \(C_i\) を加算する。

一見複雑なアルゴリズムですが、丁寧に各ステップを追えば 、各操作について \(B_{K+1}, B_{K+2}, \dots, B_{r_q-l_q+1}\) がそれぞれ答えの \({l_q+K}, {l_q+K+1}, \dots, {r_q}\) 項目にちゃんと寄与していることが確認できます。

あとは、各操作における \(B_{r_q-l_q-K+2+j}\ (0 \leq j < K)\)（すなわち、\(B\) の実際に使う部分のうち最後の \(K\) 項）を求められればよいです。ここで、以下の事実を用います。

• \(K+1\) 項間線形漸化式を \(1\) つ定めたとき、ある定数 \(D_{i, j}\ (i \geq 1, 1\leq j \leq K)\) が存在して、
  • その漸化式に従う任意の数列 \(x_1, x_2, \dots\) に対して、\(\displaystyle x_i = \sum_{j=1}^K D_{i,j}x_j \)
• 言い換えれば、ある特定の漸化式に従う数列の任意の項は初項の線型結合として表され、しかもその係数は初項によらず一定である

定数 \(D_{i,j}\) は、漸化式に従って \(i\) の昇順に求めることができ、 \(1 \leq i \leq N\) の範囲の値を \(O(NK^2)\) で求められます。これを前計算しておけば、各操作において初項が与えられたとき、\(N\) 項目までの任意の項の値が \(1\) 項あたり \(O(K)\) で求まります。よってこの問題を解くことができました。

全体の計算量は \(O((N+Q)K^2)\) です。

実装例 (C++) :

#include<bits/stdc++.h>
#include<atcoder/modint>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n), p(k);
    for (int &i: a) cin >> i;
    for (int &i: p) cin >> i;
    
    vector coef(n, vector<mint>(k));
    for (int i = 0; i < min(k, n); i++) coef[i][i] = 1;
    for (int i = k; i < n; i++) {
        for (int j = 0; j < k; j++) {
            for (int l = 0; l < k; l++) {
                coef[i][l] += coef[i - 1 - j][l] * p[j];
            }
        }
    }
    
    vector<mint> ans(n);
    for (int i = 0; i < n; i++) ans[i] = a[i];
    vector add(n + 1, vector<mint>(k));
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        vector<int> b(k);
        for (int &i: b) cin >> i;
        
        if (r - l <= k) {
            for (int i = 0; i < r - l; i++) ans[l + i] += b[i];
        } else {
            for (int i = 0; i < k; i++) {
                ans[l + i] += b[i];
                add[l + k][i] += b[i];
                mint now;
                for (int j = 0; j < k; j++) {
                    now += coef[r - k + i - l][j] * b[j];
                }
                add[r][i] -= now;
            }
        }
    }
    
    vector<mint> c(n);
    for (int i = 0; i < n; i++) {
        if(i >= k) {
            for (int j = 0; j < k; j++) c[i - k + j] += add[i][j];
            for (int j = 0; j < k; j++) c[i] += c[i - 1 - j] * p[j];
        }
        ans[i] += c[i];
    }
    
    for (int i = 0; i < n; i++) cout << ans[i].val() << " \n"[i == n - 1];
}