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:
/**
*	created: 07.09.2020 23:04:29
**/
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
using ll = long long;
// using P = pair<int,int>;
// #define endl '\n'
#define int long long
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define rrep(i,n) for (int i = (int)(n - 1); i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
const long double pi = acos(-1.0);
const int MAX = 1000010;
const int INF = 1ll << 60;
// const int MOD = 1000000007;
const int MOD = 998244353;
template<typename T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T> bool chmin(T &a, const T &b) {if (b < a) {a = b; return 1;} return 0;}
template<typename T> T pow(T a, ll n) {T r(1); while(n) {if (n & 1) r *= a; a *= a; n >>= 1;} return r;}
struct faster_io {faster_io() {cin.tie(0); ios_base::sync_with_stdio(false);}} faster_io_;

// ModInt
template <int mod> struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long x_) {if ((x = x_ % mod + mod) >= mod) x -= mod;}
    ModInt inv() const {return pow(*this, mod - 2);}
    ModInt& operator+=(ModInt rhs) {if ((x += rhs.x) >= mod) x -= mod; return *this;}
    ModInt& operator-=(ModInt rhs) {if ((x -= rhs.x) < 0) x += mod; return *this;}
    ModInt& operator*=(ModInt rhs) {x = (unsigned long long)x * rhs.x % mod; return *this;}
    ModInt& operator/=(ModInt rhs) {x = (unsigned long long)x * rhs.inv().x % mod; return *this;}
    ModInt operator-() const {return -x < 0 ? mod - x : -x;}
    ModInt operator+(ModInt rhs) const {return ModInt(*this) += rhs;}
    ModInt operator-(ModInt rhs) const {return ModInt(*this) -= rhs;}
    ModInt operator*(ModInt rhs) const {return ModInt(*this) *= rhs;}
    ModInt operator/(ModInt rhs) const {return ModInt(*this) /= rhs;}
    bool operator==(ModInt rhs) const {return x == rhs.x;}
    bool operator!=(ModInt rhs) const {return x != rhs.x;}
    friend ostream& operator<<(ostream& s, ModInt<mod> a) {s << a.x; return s;}
    friend istream& operator>>(istream& s, ModInt<mod>& a) {s >> a.x; return s;}
};

using mint = ModInt<MOD>;
using P = pair<mint,mint>;

/*
// Segment Tree with Lazy Propagation 1
template <typename X, typename M, typename FX, typename FA, typename FM> 
struct LZSegTree {
    int n; FX fx; FA fa; FM fm; const X ex; const M em;
    vector<X> dat; vector<M> lazy;
    LZSegTree(int n_, FX fx_, FA fa_, FM fm_, X ex_, M em_)
        : n(), fx(fx_), fa(fa_), fm(fm_), ex(ex_), em(em_), dat(n_*4, ex), lazy(n_*4, em) {
        int x = 1; while (n_ > x) x *= 2; n = x;
    }
    void set(int i, X x) {dat[i+n-1] = x;}
    void build() {rrep(k,n-1) dat[k] = fx(dat[2*k+1], dat[2*k+2]);}
    void eval(int k) {
        if (lazy[k] == em) return;  
        if (k < n - 1) {
            lazy[k*2+1] = fm(lazy[k*2+1], lazy[k]);
            lazy[k*2+2] = fm(lazy[k*2+2], lazy[k]);
        }
        dat[k] = fa(dat[k], lazy[k]); lazy[k] = em;
    }
    void update(int a, int b, M x) {return update_sub(a, b, x, 0, 0, n);}
    // query(a,b): f[a,b), Ο(log(n))
    X query(int a, int b) {return query_sub(a, b, 0, 0, n);}
    private:
    void update_sub(int a, int b, M x, int k, int l, int r) {
        eval(k);
        if (a <= l && r <= b) lazy[k] = fm(lazy[k], x), eval(k);
        else if (a < r && l < b) {                     
            update_sub(a, b, x, k*2+1, l, (l+r)/2);  
            update_sub(a, b, x, k*2+2, (l+r)/2, r);  
            dat[k] = fx(dat[k*2+1], dat[k*2+2]);
        }
    }
    X query_sub(int a, int b, int k, int l, int r) {
        eval(k);
        if (r <= a || b <= l) return ex;
        else if (a <= l && r <= b) return dat[k];    
        else {
            X vl = query_sub(a, b, k*2+1, l, (l+r)/2);
            X vr = query_sub(a, b, k*2+2, (l+r)/2, r);
            return fx(vl, vr);
        }
    }
};
*/

// Segment Tree with Lazy Propagation 2
template <typename X, typename M>
struct LZPSegTree {
    using FX = function<X(X, X)>;
    using FA = function<X(X, M)>;
    using FM = function<M(M, M)>;
    using FP = function<M(M, int)>;
    int n;  FX fx;  FA fa;  FM fm;  FP fp; 
    const X ex;  const M em;
    vector<X> dat; vector<M> lazy;
    LZPSegTree(int n_,FX fx_,FA fa_,FM fm_,FP fp_,X ex_,M em_)
        : n(),fx(fx_),fa(fa_),fm(fm_),fp(fp_),ex(ex_),em(em_),dat(n_*4,ex),lazy(n_*4,em) {
        int x = 1; while (n_> x) {x *= 2;} n = x;
    }
    void set(int i, X x) {dat[i+n-1] = x; return;}
    void build() {rrep(k,n-1) dat[k] = fx(dat[2*k+1], dat[2*k+2]); return;}
    void eval(int k, int len) {
        if (lazy[k] == em) return; 
        if (k < n - 1) {          
            lazy[k*2+1] = fm(lazy[k*2+1], lazy[k]);
            lazy[k*2+2] = fm(lazy[k*2+2], lazy[k]);
        }
        dat[k] = fa(dat[k],fp(lazy[k],len)); lazy[k] = em;
        return;
    }
    void update(int a, int b, M x) {update_sub(a, b, x, 0, 0, n); return;}
    X query(int a, int b) {return query_sub(a, b, 0, 0, n);}
    private:
    void update_sub(int a, int b, M 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);
            return;
        }
        else if (a < r && l < b) {
            update_sub(a, b, x, k*2+ 1, l, (l+r)/2);
            update_sub(a, b, x, k*2+2, (l+r)/2, r);
            dat[k] = fx(dat[k*2+1], dat[k*2+2]);
            return;
        }
    }
    X query_sub(int a, int b, int k, int l, int r) {
        eval(k, r - l);
        if (r <= a || b <= l) return ex;
        else if (a <= l && r <= b) return dat[k];
        else { 
            X vl = query_sub(a, b, k*2+1, l, (l+r)/2);
            X vr = query_sub(a, b, k*2+2, (l+r)/2, r);
            return fx(vl, vr);
        }
    }
    
};

signed main() {
    int n, q; cin >> n >> q;
    using X = mint;
    using M = P;
    auto fx = [](X x1, X x2) -> X {return x1 + x2;};
    auto fa = [](X x, M m) -> X {return m.first * x + m.second;};
    auto fm = [](M m1, M m2) -> M {return P(m1.first*m2.first, m2.first*m1.second + m2.second);};
    auto fp = [](M m, int n) -> M {return P(m.first, m.second*n);};
    X ex = 0;
    M em = P(1,0);
    LZPSegTree<X, M> rzseg(n,fx,fa,fm,fp,ex,em);
    rep(i,n) {
        int a; cin >> a;
        rzseg.set(i,a);
    }
    rzseg.build();
    rep(i,q) {
        int t, l, r; cin >> t >> l >> r;
        if(t) {
            cout << rzseg.query(l,r) << endl;
        }
        else {
            mint b, c; cin >> b >> c;
            rzseg.update(l,r,P(b,c));
        }
    }
    return 0;
}