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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring>
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ
//vector<vector<ll>> dp(n,vector<ll>(n))
//2-dim:vector<vector<Type>> vv(n, vector<Type>(m, d));
//3-dim:vector<vector<vector<Type>>> vvv(n, vector<vector<Type>>(m, vector<Type>(l, d)));

// 内部実装は1-indexed
template<typename T,typename E>
struct LazySegmentTree{
    using F = function<T(T,T)>;
    using G = function<T(T,E)>;
    using H = function<E(E,E)>;
    int sz_,height;
    F f; G g; H h;
    T identity_T;
    E identity_E;
    vector<T> node;
    vector<E> lazy;
    LazySegmentTree(F f_,G g_,H h_,T identity_T_,E identity_E_):
        f(f_),g(g_),h(h_),identity_T(identity_T_),identity_E(identity_E_){}
    void init(int n_){
        sz_=1; height=0;
        while(sz_<n_){ sz_<<=1; height++; }
        node.assign(2*sz_,identity_T);
        lazy.assign(2*sz_,identity_E);
    }
    void build(vector<T> &v){
        int n_=(int)v.size();
        init(n_);
        for(int i_=0;i_<sz_;i_++){
            node[sz_+i_]=v[i_];
        }
        for(int i_=sz_-1;i_;i_--){
            node[i_]=f(node[(i_<<1)|0],node[(i_<<1)|1]);
        }
    }
    inline T reflect(int k_){
        return lazy[k_]==identity_E ? node[k_] :g(node[k_],lazy[k_]);
    }
    inline void thrust(int k_){
        for(int i_=height;i_;i_--) eval(k_>>i_);
    }
    inline void recalc(int k_){
        while(k_>>=1){
            node[k_]=f(reflect((k_<<1)|0),reflect((k_<<1)|1));
        }
    }
    inline void eval(int k_){
        if(lazy[k_]==identity_E) return;
        lazy[(k_<<1)|0]=h(lazy[(k_<<1)|0],lazy[k_]);
        lazy[(k_<<1)|1]=h(lazy[(k_<<1)|1],lazy[k_]);
        node[k_]=reflect(k_);
        lazy[k_]=identity_E;
    }
    void update(int a,int b,E x_){
        thrust(a+=sz_);
        thrust(b+=sz_-1);
        for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
            if(l&1){ lazy[l]=h(lazy[l],x_); ++l; }
            if(r&1){ --r; lazy[r]=h(lazy[r],x_); }
        }
        recalc(a);
        recalc(b);
    }
    void set_val(int a,T x){
      thrust(a+=sz_);
      node[a]=x; lazy[a]=identity_E;
      recalc(a);
    }
    T query(int a,int b){
      //assert(0<=a&&a<=b&&b<=sz_);
      thrust(a+=sz_);
      thrust(b+=sz_-1);
      T vl=identity_T,vr=identity_T;
      for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
        if(l&1) vl=f(vl,reflect(l++));
        if(r&1) vr=f(reflect(--r),vr);
      }
      return f(vl,vr);
    }
};

signed main(){
    const ll MOD = 998244353;
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    int n,q; cin >> n >> q;
    auto f=[](Pll a,Pll b){
        return Pll{(a.fi+b.fi)%MOD,a.se+b.se};
    };
    auto g=[](Pll a,Pll b){
        return Pll{(a.fi*b.fi+b.se*a.se)%MOD,a.se};
    };
    auto h=[](Pll a,Pll b){
        return Pll{(a.fi*b.fi)%MOD,(a.se*b.fi+b.se)%MOD};
    };
    int sz=1;
    while(sz<n) sz*=2;
    vector<Pll> v(sz,{0,1});
    rep(i,n) cin >> v[i].fi;
    //T,E
    LazySegmentTree<Pll,Pll> lst(f,g,h,{0,0},{1,0});
    lst.build(v);
    rep(i,q){
        int x; cin >> x;
        int s,t; cin >> s >> t;
        if(x==0){
            ll a,b; cin >> a >> b;
            lst.update(s,t,{a,b});
        }else{
            cout << lst.query(s,t).fi << "\n";
        }
    }
}
