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;

typedef long long ll;
typedef pair<int,int> P;

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

template<typename T1,typename T2>ostream& operator<<(ostream& os,const pair<T1,T2>& a) {os << "(" << a.first << ", " << a.second << ")";return os;}

const char newl = '\n';
ll const mod = 998244353;

struct LazySegmentTree {
private:
    int n;
    vector<ll> node,lazy_b,lazy_c;
    vector<bool> upd;
public:
    LazySegmentTree(vector<ll> v) {
        int sz = v.size();
        n = 1;
        while (n < sz) n *= 2;
        node.resize(2*n-1);
        lazy_b.resize(2*n-1,1);
        lazy_c.resize(2*n-1,0);
        upd.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] = (node[i*2+1]+node[i*2+2])%mod;
    }

    void eval(int k,int l,int r) {
        if (upd[k]) {
            (node[k] *= lazy_b[k]) %= mod;
            (node[k] += lazy_c[k]*(r-l)%mod) %= mod;
            if (r-l > 1) {
                (lazy_b[2*k+1] *= lazy_b[k]) %= mod;
                (lazy_b[2*k+2] *= lazy_b[k]) %= mod;
                (lazy_c[2*k+1] *= lazy_b[k]) %= mod;
                (lazy_c[2*k+2] *= lazy_b[k]) %= mod;
                (lazy_c[2*k+1] += lazy_c[k]) %= mod;
                (lazy_c[2*k+2] += lazy_c[k]) %= mod;
                upd[2*k+1] = upd[2*k+2] = true;
            }
            lazy_b[k] = 1;
            lazy_c[k] = 0;
            upd[k] = false;
        }
    }

    void update(int a,int b,ll x,ll y,int k = 0,int l = 0,int r = -1) {
        if (r < 0) r = n;
        eval(k,l,r);
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            lazy_b[k] = x;
            lazy_c[k] = y;
            upd[k] = true;
            eval(k,l,r);
        } else {
            update(a,b,x,y,2*k+1,l,(l+r)/2);
            update(a,b,x,y,2*k+2,(l+r)/2,r);
            node[k] = (node[2*k+1]+node[2*k+2])%mod;
        }
    }

    ll getsum(int a,int b,int k = 0,int l = 0,int r = -1) {
        if (r < 0) r = n;
        if (b <= l || r <= a) return 0;
        eval(k,l,r);
        if (a <= l && r <= b) return node[k];
        ll vl = getsum(a,b,k*2+1,l,(l+r)/2);
        ll vr = getsum(a,b,2*k+2,(l+r)/2,r);
        return (vl+vr)%mod;
    }
};

int main() {
    int n,q;
    cin >> n >> q;
    vector<ll> a(n);
    for (int i = 0;i < n;++i) cin >> a[i];
    LazySegmentTree seg(a);
    for (int i = 0;i < q;++i) {
        int t,l,r;
        cin >> t >> l >> r;
        if (t) cout << seg.getsum(l,r) << newl;
        else {
            int b,c;
            cin >> b >> c;
            seg.update(l,r,b,c);
        }
    }
}