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>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
#include <cstring>
using namespace std;

using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1001001001;
// constexpr int mod = 1000000007;
constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template<int mod>
struct ModInt{
    int x;

    ModInt() : x(0) {}
    
    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    
    ModInt &operator+=(const ModInt &p){
        if((x += p.x) >= mod)   x -= mod;
        return *this;
    }
    
    ModInt &operator-=(const ModInt &p){
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p){
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p){
        *this *= p.inverse();
        return *this;
    }
    
    ModInt operator-() const {return ModInt(-x);}

    ModInt operator+(const ModInt &p) const {return ModInt(*this) += p;}

    ModInt operator-(const ModInt &p) const {return ModInt(*this) -= p;}

    ModInt operator*(const ModInt &p) const {return ModInt(*this) *= p;}

    ModInt operator/(const ModInt &p) const {return ModInt(*this) /= p;}

    bool operator==(const ModInt &p) const {return x == p.x;}

    bool operator!=(const ModInt &p) const {return x != p.x;}

    ModInt inverse() const{
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0){
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const{
        ModInt ret(1), mul(x);
        while(n > 0){
            if(n & 1)   ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p){
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a){
        int64_t t;
        is >> t;
        a = ModInt<mod>(t);
        return (is);
    }

    static int get_mod() {return mod;}
};

using modint = ModInt<mod>;

struct LazySegmentTree{
    vector<modint> data;
    vector<modint> mul, add;
    int sz;

    LazySegmentTree(int n){
        sz = 1;
        while(sz < n)   sz <<= 1;
        data.resize(sz << 1, 0);
        mul.resize(sz << 1, 1);
        add.resize(sz << 1, 0);
    }

    void set(int k, const modint& x) { data[sz + k] = x; }

    void build(){
        for(int k = sz - 1; k > 0; --k){
            data[k] = data[k << 1] + data[k << 1 | 1];
        }
    }

    void propagate(int k, int len){
        if(mul[k] == 1 && add[k] == 0)  return;
        if(k < sz){
            mul[k << 1] *= mul[k];
            add[k << 1] = mul[k] * add[k << 1] + add[k];
            mul[k << 1 | 1] *= mul[k];
            add[k << 1 | 1] = mul[k] * add[k << 1 | 1] + add[k];
        }
        data[k] = mul[k] * data[k] + add[k] * len;
        mul[k] = 1, add[k] = 0;
    }

    modint update(int a, int b, const modint& x, const modint& y, int k = 1, int l = 0, int r = -1){
        if(r == -1) r = sz;
        propagate(k, r - l);
        if(b <= l || r <= a)    return data[k];
        else if(a <= l && r <= b){
            mul[k] *= x;
            add[k] += y;
            propagate(k, r - l);
            return data[k];
        }
        else{
            return data[k] = update(a, b, x, y, k << 1, l, (l + r) >> 1)
                            + update(a, b, x, y, k << 1 | 1, (l + r) >> 1, r);
        }
    }

    modint query(int a, int b, int k = 1, int l = 0, int r = -1){
        if(r == -1) r = sz;
        propagate(k, r - l);
        if(b <= l || r <= a)    return 0;
        else if(a <= l && r <= b)   return data[k];
        else{
            return query(a, b, k << 1, l, (l + r) >> 1)
                    + query(a, b, k << 1 | 1, (l + r) >> 1, r);
        }
    }

    modint operator[](int& k) { return query(k, k + 1); }

    int size() const { return sz; }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q, a;
    cin >> N >> Q;
    LazySegmentTree seg(N);
    for(int i = 0; i < N; ++i){
        cin >> a;
        seg.set(i, a);
    }
    seg.build();
    for(int i = 0; i < Q; ++i){
        int T, l, r;
        cin >> T >> l >> r;
        if(T)   cout << seg.query(l, r) << '\n';
        else{
            modint b, c;
            cin >> b >> c;
            seg.update(l, r, b, c);
        }
    }
}