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 <vector>

using namespace std;

// ax+b -> c(ax+b) + d = acx + bc + d

const int MOD = 998244353;

template<typename T>
class LazySegTree {
public:
    explicit LazySegTree(int n, vector<T> init, T def) : N(calcN_(n)), def(def) {
        mVal.assign(2*N-1, 0);
        for(int i=0;i<init.size();i++) mVal[N-1+i] = init[i];
        for(int i=N-2;i>=0;i--) mVal[i] = operate_(mVal[2*i+1], mVal[2*i+2]);
        mLazy.assign(2*N-1, make_pair(1, 0));
        mDirty.assign(2*N-1, 0);
    }
    void update(int l, int r, pair<long long, long long> value){
        updateImpl_(l, r, value, 0, 0, N);
    }
    T get(int l, int r){
        return getImpl_(l, r, 0, 0, N);
    }
private:
    int calcN_(int n){
        int res = 1;
        while(res < n) res *= 2;
        return res;
    }
    void updateImpl_(int l, int r, pair<long long, long long> value, int idx, int rangeL, int rangeR){
        eval_(idx, rangeL, rangeR);
        if(r <= rangeL || rangeR <= l) return;
        if(l <= rangeL && rangeR <= r){
            setLazy_(idx, value);
            eval_(idx, rangeL, rangeR);
        } else {
            int rangeM = (rangeL+rangeR)/2;
            updateImpl_(l, r, value, 2*idx+1, rangeL, rangeM);
            updateImpl_(l, r, value, 2*idx+2, rangeM, rangeR);
            mVal[idx] = operate_(mVal[2*idx+1], mVal[2*idx+2]);
        }
    }
    void setLazy_(int idx, pair<long long, long long> value){
        auto cur = mLazy[idx];
        mLazy[idx].first = (cur.first * value.first) % MOD;
        mLazy[idx].second = (cur.second * value.first + value.second) % MOD;
        mDirty[idx] = 1;
    }
    T getImpl_(int l, int r, int idx, int rangeL, int rangeR){
        if(r <= rangeL || rangeR <= l) return def;
        eval_(idx, rangeL, rangeR);
        if(l <= rangeL && rangeR <= r) return mVal[idx];
        int rangeM = (rangeL+rangeR)/2;
        T a = getImpl_(l, r, 2*idx+1, rangeL, rangeM);
        T b = getImpl_(l, r, 2*idx+2, rangeM, rangeR);
        return operate_(a, b);
    }
    void eval_(int idx, int rangeL, int rangeR){
        if(!mDirty[idx]) return;
        mVal[idx] = (mLazy[idx].first * mVal[idx] + (rangeR - rangeL) * mLazy[idx].second) % MOD;
        if(idx < N-1){
            setLazy_(2*idx+1, mLazy[idx]);
            setLazy_(2*idx+2, mLazy[idx]);
        }
        mLazy[idx] = make_pair(1, 0);
        mDirty[idx] = 0;
    }
    T operate_(T a, T b) const { return (a + b) % MOD; }
    const int N;
    const T def;
    vector<T> mVal;
    vector<pair<long long, long long>> mLazy;
    vector<int> mDirty;
};

int main(){
    int N, Q; cin >> N >> Q;
    vector<long long> a(N);
    for(auto& t : a) cin >> t;
    LazySegTree<long long> seg(N, a, 0);
    for(int i=0;i<Q;i++){
        int t; cin >> t;
        if(t == 0){
            int l, r, b, c; cin >> l >> r >> b >> c;
            seg.update(l, r, make_pair(b, c));
        } else {
            int l, r; cin >> l >> r;
            cout << seg.get(l, r) << endl;
        }
    }
}