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 <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

#define debug_value(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << #x << "=" << x << endl;
#define debug(x) cerr << "line" << __LINE__ << ":<" << __func__ << ">:" << x << endl;

using namespace std;
typedef long long ll;

const ll MOD = 998244353;

struct affine{
    ll b, c;
};

affine unit_affine = (affine){1, 0};

bool is_unit(affine n){
    return n.b == 1 && n.c == 0;
}

// b(a(x))
affine merge_affine(affine a, affine b){
    if(is_unit(a)) return b;
    if(is_unit(b)) return a;
    return (affine){(b.b*a.b)%MOD, (b.b*a.c+b.c)%MOD};
}

ll apply_affine(ll n, affine a){
    return (n*a.b+a.c)%MOD;
}

struct node{
    ll cnt, n;
};

node merge_node(node a, node b){
    return (node){a.cnt+b.cnt, (a.n+b.n)%MOD};
}

template <typename T, typename S>
struct LazySegmentTree {
    int n;
    T unit;
    vector<T> node;
    vector<S> lazy;
    vector<bool> lazyFlag;

    T calc(T a, T b){
        T ans;
        ans = merge_node(a, b); //適宜変える
        return ans;
    }

    S calcLazy(S a, S b){
        S ans;
        ans = merge_affine(a, b); //適宜変える
        return ans;
    }

    S propagateLazy(S lazy1, S lazy2){
        return merge_affine(lazy1, lazy2); //適宜変える
    }

    T merge(T n, S lazy){
        return {n.cnt, (n.n*lazy.b+lazy.c*n.cnt)%MOD }; //適宜変える
    }

    S clearLazy(){
        return unit_affine; //適宜変える
    }

    LazySegmentTree(vector<T> v, T UNIT, S UNIT_LAZY) {
        int sz = (int)v.size();
        unit = UNIT;
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, unit);
        lazy.resize(2*n-1, UNIT_LAZY);
        lazyFlag.resize(2*n-1, false);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = calc(node[i*2+1], node[i*2+2]);
    }

    void lazyEvaluate(int k, int l, int r) {
        if(lazyFlag[k]) {
            node[k] = merge(node[k], lazy[k]);
            if(r - l > 1) {
                lazy[k*2+1] = propagateLazy(lazy[k*2+1], lazy[k]);
                lazy[k*2+2] = propagateLazy(lazy[k*2+2], lazy[k]);
                lazyFlag[k*2+1] = lazyFlag[k*2+2] = true;
            }
            lazyFlag[k] = false;
            lazy[k] = clearLazy();
        }
    }

    //[a, b)
    //区間[a, b]への更新に対してはupdate(a, b+1, x)と呼ぶ
    void update(int a, int b, S x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        lazyEvaluate(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] = calcLazy(lazy[k], x);
            lazyFlag[k] = true;
            lazyEvaluate(k, l, r);
        }
        else {
            update(a, b, x, 2*k+1, l, (l+r)/2);
            update(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = calc(node[2*k+1], node[2*k+2]);
        }
    }

    //[a, b)
    //区間[a, b]へのクエリに対してはquery(a, b+1)と呼ぶ
    T query(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        lazyEvaluate(k, l, r);
        if(b <= l || r <= a) return unit;
        if(a <= l && r <= b) return node[k];
        T vl = query(a, b, 2*k+1, l, (l+r)/2);
        T vr = query(a, b, 2*k+2, (l+r)/2, r);
        return calc(vl, vr);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int N, Q; cin >> N >> Q;
    vector<node> a(N);
    for(int i = 0; i < N; i++) {
        ll s; cin >> s;
        a[i] = (node){1, s};
    }
    LazySegmentTree<node, affine> sgt(a, (node){1, 0}, unit_affine);
    for(int i = 0; i < Q; i++){
        int t; cin >> t;
        if(t == 0){
            int l, r; ll b, c; cin >> l >> r >> b >> c;
            sgt.update(l, r, (affine){b, c});
        }else{
            int l, r; cin >> l >> r;
            cout << sgt.query(l, r).n << endl;
        }
        
    }
}