Problem: You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

* `0 l r b c`: For each i = l, l+1, \dots, {r - 1}, set a_i \gets b \times a_i + c.
* `1 l r`: Print \sum_{i = l}^{r - 1} a_i \bmod 998244353.

Constraints

* 1 \leq N, Q \leq 500000
* 0 \leq a_i, c < 998244353
* 1 \leq b < 998244353
* 0 \leq l < r \leq N
* All values in Input are integer.

Input

Input is given from Standard Input in the following format:


N Q
a_0 a_1 ... a_{N - 1}
\textrm{Query}_0
\textrm{Query}_1
:
\textrm{Query}_{Q - 1}


Output

For each query of the latter type, print the answer.

Example

Input

5 7
1 2 3 4 5
1 0 5
0 2 4 100 101
1 0 3
0 1 3 102 103
1 2 5
0 2 5 104 105
1 0 5


Output

15
404
41511
4317767

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(12), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
using Int = long long;
const Int MOD = 998244353;
struct SegTree {
    int N;
    vector<Int> A, B, C;
    SegTree(int n) {
        N = 1; while (N < n) N *= 2;
        A.resize(2 * N);
        B.resize(2 * N, 1);
        C.resize(2 * N);
    }
    void build(const vector<Int> &ary) {
        fill(begin(A), end(A), 0);
        fill(begin(B), end(B), 1);
        fill(begin(C), end(C), 0);
        for (int i = 0; i < ary.size(); i++) {
            A[N + i] = ary[i];
        }
        for (int i = N - 1; i > 0; i--) {
            A[i] = (A[2*i+0] + A[2*i+1]) % MOD;
        }
    }
    Int sum_0(int L, int R, int node, int nodeL, int nodeR) {
        if (R <= nodeL || nodeR <= L) return 0;
        if (L <= nodeL && nodeR <= R) return A[node];
        A[2*node+0] = (B[node] * A[2*node+0] + C[node] * (nodeR - nodeL) / 2) % MOD;
        A[2*node+1] = (B[node] * A[2*node+1] + C[node] * (nodeR - nodeL) / 2) % MOD;
        B[2*node+0] = B[node] * B[2*node+0] % MOD;
        B[2*node+1] = B[node] * B[2*node+1] % MOD;
        C[2*node+0] = (B[node] * C[2*node+0] + C[node]) % MOD;
        C[2*node+1] = (B[node] * C[2*node+1] + C[node]) % MOD;
        B[node] = 1, C[node] = 0;
        Int ans = 0;
        ans += sum_0(L, R, 2*node+0, nodeL, (nodeL + nodeR) / 2);
        ans += sum_0(L, R, 2*node+1, (nodeL + nodeR) / 2, nodeR);
        return ans % MOD;
    }
    Int sum(int L, int R) {
        return sum_0(L, R, 1, 0, N);
    }
    void modify_0(int L, int R, int b, int c, int node, int nodeL, int nodeR) {
        if (R <= nodeL || nodeR <= L) return;
        if (L <= nodeL && nodeR <= R) {
            A[node] = (b * A[node] + (Int)c * (nodeR - nodeL)) % MOD;
            B[node] = b * B[node] % MOD;
            C[node] = (b * C[node] + c) % MOD;
            return;
        }
        A[2*node+0] = (B[node] * A[2*node+0] + C[node] * (nodeR - nodeL) / 2) % MOD;
        A[2*node+1] = (B[node] * A[2*node+1] + C[node] * (nodeR - nodeL) / 2) % MOD;
        B[2*node+0] = B[node] * B[2*node+0] % MOD;
        B[2*node+1] = B[node] * B[2*node+1] % MOD;
        C[2*node+0] = (B[node] * C[2*node+0] + C[node]) % MOD;
        C[2*node+1] = (B[node] * C[2*node+1] + C[node]) % MOD;
        B[node] = 1, C[node] = 0;
        modify_0(L, R, b, c, 2*node+0, nodeL, (nodeL + nodeR) / 2);
        modify_0(L, R, b, c, 2*node+1, (nodeL + nodeR) / 2, nodeR);
        A[node] = (A[2*node+0] + A[2*node+1]) % MOD;
    }
    void modify(int L, int R, int b, int c) {
        modify_0(L, R, b, c, 1, 0, N);
    }
};
int main() {
    int N, Q; cin >> N >> Q;
    vector<Int> A(N); for (auto &a : A) cin >> a;
    SegTree st(N);
    st.build(A);
    for (int i = 0; i < Q; i++) {
        int type; cin >> type;
        if (type == 0) {
            int l, r, b, c; cin >> l >> r >> b >> c;
            st.modify(l, r, b, c);
        } else {
            int l, r; cin >> l >> r;
            cout << st.sum(l, r) << '\n';
        }
    }
    return 0;
}