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;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
const ll mod = 998244353;
const int maxn = 5e5+5;
ll sum[maxn<<2];
ll mul[maxn<<2];
ll add[maxn<<2];
void pull(int x) {
    sum[x] = (sum[x<<1] + sum[x<<1|1]) % mod;
}


void push(int x,int l,int r,int mid) {
    if (mul[x] != -1) {
        if (~mul[x<<1]) {
            mul[x<<1] *= mul[x];
            mul[x<<1] %= mod;
        }
        else {
            mul[x<<1] = mul[x];
        }
        sum[x<<1] *= mul[x];
        sum[x<<1] %= mod;
        if (~add[x<<1]) {
            add[x<<1] *= mul[x];
            add[x<<1] %= mod;
        }
        if (~mul[x<<1|1]) {
            mul[x<<1|1] *= mul[x];
            mul[x<<1|1] %= mod;
        }
        else {
            mul[x<<1|1] = mul[x];
        }
        sum[x<<1|1] *= mul[x];
        sum[x<<1|1] %= mod;
        if (~add[x<<1|1]) {
            add[x<<1|1] *= mul[x];
            add[x<<1|1] %= mod;
        }
        mul[x] = -1;
    }
    if (add[x] != -1) {
        if (!(~add[x<<1])) {
            add[x<<1] = add[x];
        }
        else {
            add[x<<1] += add[x];
            add[x<<1] %= mod;
        }
        sum[x<<1] += (mid-l+1) * add[x] % mod;
        sum[x<<1] %= mod;
        if (!(~add[x<<1|1])) {
            add[x<<1|1] = add[x];
        }
        else {
            add[x<<1|1] += add[x];
            add[x<<1|1] %= mod;
        }
        sum[x<<1|1] += (r - mid) * add[x] % mod;
        sum[x<<1|1] %= mod;
        add[x] = -1;
    }
}
void update(int x,int l,int r,int ql,int qr,int ad,int mu) {
    if (ql <= l && qr >= r) {
        sum[x] *= mu;
        sum[x] %= mod;
        sum[x] += (ll)(r - l + 1) * ad;
        sum[x] %= mod;
        if (mul[x] == -1) {
            mul[x] = mu;
        }
        else {
            mul[x] *= mu;
            mul[x] %= mod;
        }
        if (add[x] != -1) {
            add[x] *= mu;
            add[x] %= mod;
        }
        if (add[x] == -1) {
            add[x] = ad;
        }
        else {
            add[x] += ad;
            add[x] %= mod;
        }
        return;
    }
    int mid = (l + r) >> 1;
    push(x,l,r,mid);
    if (ql <= mid) {
        update(x<<1,l,mid,ql,qr,ad,mu);
    }
    if (qr > mid) {
        update(x<<1|1,mid+1,r,ql,qr,ad,mu);
    }
    pull(x);
}
ll query(int x,int l,int r,int ql,int qr) {
    if (ql <= l && qr >= r) {
        return sum[x];
    }
    int mid = (l + r) >> 1;
    push(x,l,r,mid);
    if (qr <= mid) {
        return query(x<<1,l,mid,ql,qr);
    }
    if (ql > mid) {
        return query(x<<1|1,mid+1,r,ql,qr);
    }
    return (query(x<<1,l,mid,ql,qr) + query(x<<1|1,mid+1,r,ql,qr)) % mod;
}
void build(int x,int l,int r) {
    if (l == r) {
        cin >> sum[x];
        return;
    }
    int mid = (l + r) >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pull(x);
}
void solve() {
    int n, q;
    cin >> n >> q;
    memset(add, -1, sizeof(add));
    memset(mul,-1, sizeof(mul));
    build(1,1,n);
    while (q--) {
        int op,l,r;
        cin >> op >> l >> r;
        l++;
        if (op == 0) {
            int a, b;
            cin >> a >> b;
            update(1,1,n,l,r,b,a);
        }
        else {
            cout << query(1,1,n,l,r) << '\n';
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int c = 0;
    int t;
    if (!c) {
        t = 1;
    }
    else {
        cin >> t;
    }
    while (t--) {
        solve();
    }
    
}