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 <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvv vector<vvl>
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
//typedef __int128_t lll;
using namespace std;

#define mod 998244353

struct affine{
  ll a=1, b=0;
  affine(ll A, ll B){a=A,b=B;}
};

affine unit(1, 0);
ll ff(ll a, ll b){return (a+b)%mod;}
ll gg(ll a, affine b){return ((a*b.a)%mod+b.b)%mod;}


affine hh(affine a, affine b){
  return affine((a.a*b.a)%mod, ((a.b*b.a)%mod + (b.b)%mod)%mod);
}
//*499122177
affine pp(affine a, ll len){
  return affine(a.a, a.b*len);
}
template <typename T, typename E> // dat lazy
struct segtree{
  vector<T> dat;vector<E> laz;
  typedef function<T(T, T)> F; //dat - datのマージ
  typedef function<T(T, E)> G; //dat - lazyのマージ
  typedef function<E(E, E)> H; //lazy - lazyの更新
  typedef function<E(E, int)> P; //lazy - lenの関数
  int n;F f;G g;H h;P p;
  T dat_unit;
  E lazy_unit;

  segtree(int m,T dat_unit_,E lazy_unit_, F ff,G gg,H hh,P pp=[](E a,int b){return a;}):dat_unit(dat_unit_),lazy_unit(lazy_unit_){
    f = ff, g = gg, h = hh, p = pp;
    init(m);
  }

  void init(int m){
    n = 1;
    while(n<m) n*=2;
    dat.resize(2*n-1, dat_unit);
    laz.resize(2*n-1, lazy_unit);
  }

  inline void eval(int k, int l, int r){
    if(laz[k].a==1&&laz[k].b==0) return;
    if(r-l>1){
      laz[k*2+1]=h(laz[k*2+1], laz[k]);
      laz[k*2+2]=h(laz[k*2+2], laz[k]);
    }
    dat[k]=g(dat[k], p(laz[k], r - l));
    laz[k]=lazy_unit;
  }

  T update(int a, int b, E x, int k, int l, int r){
    eval(k, l, r);
    if(r<=a||b<=l) return dat[k];
    if(a<=l&&r<=b){
      laz[k] = h(laz[k], x);
      return g(dat[k], p(laz[k], r-l));
    }
    T A = update(a,b,x,k*2+1,l,(l+r)/2);
    T B = update(a,b,x,k*2+2,(l+r)/2,r);
    return dat[k] = f(A, B);
  }

  T query(int a, int b, int k, int l, int r){
    eval(k, l, r);
    if(r<=a||b<=l) return dat_unit;
    if(a<=l&&r<=b) return dat[k];
    T vl = query(a, b, k*2+1, l, (l+r)/2);
    T vr = query(a, b, k*2+2, (l+r)/2, r);
    return f(vl, vr);
  }

  T update(int a,int b, E x){return update(a,b,x,0,0,n);}
  T query(int a,int b){return query(a,b,0,0,n);}
};


int main(int argc, char const *argv[]) {
  ll n, q;std::cin >> n >> q;

  segtree<ll, affine> seg(n, 0, unit, ff, gg, hh, pp);
  re(i, n){
    ll a;scanf("%lld", &a);
    seg.update(i, i+1, affine(0, a));
  }
  re(i, q){
    ll a, b, c;scanf("%lld %lld %lld", &a, &b, &c);
    if(a) std::cout << seg.query(b, c) << '\n';
    else{
      ll d, e;scanf("%lld %lld", &d, &e);
      seg.update(b, c, affine(d, e));
    }
  }
  return 0;
}