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 <iomanip>
#include <algorithm>
#include <assert.h>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,a) for(ll i=ll(a-1);i>=0;--i)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}

const ll INF = 1e18;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const ll MOD3 = 1e6;
const ll EPS = 1e-10;
int sgn(const double a){
    return (a < -EPS ? -1 : (a > EPS ? +1 : 0));
}
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> tri;
typedef pair<long double,long double> point;
typedef complex<long double> Point;
const ll MAX = 3000;
constexpr ll nx[4] = {-1,0,1,0};
constexpr ll ny[4] = {0,1,0,-1};
template <class T1,class T2> // T1が要素、T2が作用素
class LazySegTree2 { // 区間長に比例したものを扱える
    public:
    int siz;
    typedef function<T1(T1,T1)> FX;
    typedef function<T1(T1,T2)> FA;
    typedef function<T2(T2,T2)> FM;
    typedef function<T2(T2,int)> FP;
    FX fx;
    FA fa;
    FM fm;
    FP fp;
    T1 idx;
    T2 idm;
    vector<T1> data;
    vector<T2> lazy;
    // 単位元埋め
    LazySegTree2 (int n,T1 _idx,T2 _idm,FX _fx,FA _fa,FM _fm,FP _fp):idx(_idx),idm(_idm),fx(_fx),fa(_fa),fm(_fm),fp(_fp){
        siz = 1;
        while(siz < n){
            siz *= 2;
        }
        data = vector<T1>(siz*2-1,_idx);
        lazy = vector<T2>(siz*2-1,_idm);
    }
    // 配列埋め
    LazySegTree2 (int n,T1 _idx,T2 _idm,vector<T1> &v,FX _fx,FA _fa,FM _fm,FP _fp):idx(_idx),idm(_idm),fx(_fx),fa(_fa),fm(_fm),fp(_fp){
        siz = 1;
        while(siz < n){
            siz *= 2;
        }
        data = vector<T1>(siz*2-1,_idx);
        lazy = vector<T2>(siz*2-1,_idm);
        rep(i,n){
            data[siz-1+i] = v[i];
        }
        for (int i = siz-2;i >= 0;i--){
            data[i] = fx(data[i*2+1],data[i*2+2]);
        }
    }
    //　評価関数
    void eval(int k,int len){
        if (lazy[k] == idm) return;
        if (k < siz-1){
            lazy[k*2+1] = fm(lazy[k*2+1],lazy[k]);
            lazy[k*2+2] = fm(lazy[k*2+2],lazy[k]);
        }
        data[k] = fa(data[k],fp(lazy[k],len));
        lazy[k] = idm;
    }
    // 更新クエリ
    void _update(int a,int b,T2 x,int k,int l,int r){
        eval(k,r-l);
        if (a <= l && r <= b){
            lazy[k] = fm(lazy[k],x);
            eval(k,r-l);
        }
        else if (a < r && l < b){
            _update(a,b,x,k*2+1,l,(l+r)/2);
            _update(a,b,x,k*2+2,(l+r)/2,r);
            data[k] = fx(data[k*2+1],data[k*2+2]);
        }
    }
    void update(int a,int b,T2 x){
        _update(a,b,x,0,0,siz);
    }
    // 区間クエリ
    T1 _query(int a,int b,int k,int l,int r){
        eval(k,r-l);
        if (r <= a || b <= l){
            return idx;
        }
        else if (a <= l && r <= b){
            return data[k];
        }
        else{
            T1 r1 = _query(a,b,k*2+1,l,(l+r)/2);
            T1 r2 = _query(a,b,k*2+2,(l+r)/2,r);
            return fx(r1,r2);
        }
    }
    T1 query(int a,int b){
        return _query(a,b,0,0,siz);
    }
    T1 operator[](int i){
        return query(i,i+1);
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,q;
    cin >> n >> q;
    vector<ll> a(n);
    cins(all(a));
    auto fx = [](ll a,ll b){return (a+b)%MOD2;};
    auto fa = [](ll a,P b){return (a*b.first%MOD2+b.second)%MOD2;};
    auto fm = [](P a,P b){return (P(a.first*b.first%MOD2,(b.first*a.second%MOD2+b.second)%MOD2));};
    auto fp = [](P a,int l){return P(a.first,a.second*l);};
    LazySegTree2<ll,P> s(n,0,P(1,0),a,fx,fa,fm,fp);
    rep(i,q){
        ll f;
        cin >> f;
        if (!f){
            ll l,r,b,c;
            cin >> l >> r >> b >> c;
            s.update(l,r,P(b,c));
        }
        else{
            ll l,r;
            cin >> l >> r;
            PRINT(s.query(l,r));
        }
    }
}