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:
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

template <class S, class F>
struct SegTreeL {
  using FX = function<S(S, S)>;
  using FA = function<S(S, F)>;
  using FF = function<F(F, F)>;
  int n, _n, log;
  FX fx;
  FA fa;
  FF ff;
  const S es;
  const F ef;
  vector<S> dat;
  vector<F> laz;
  SegTreeL(int n_, FX fx_, FA fa_, FF ff_, S es_, F ef_)
    : fx(fx_), fa(fa_), ff(ff_), es(es_), ef(ef_), n(1), _n(n_), log(__builtin_ctz(n_)) {
      while(n_ > n) n <<= 1;
      dat.assign(n*2-1, es);
      laz.assign(n*2-1, ef);
  }
  SegTreeL(vector<S> &v, FX fx_, FA fa_, FF ff_, S es_, F ef_)
    : fx(fx_), fa(fa_), ff(ff_), es(es_), ef(ef_), n(1), _n(int(v.size())), log(__builtin_ctz(_n)) {
      while(_n > n) n <<= 1;
      dat.assign(n*2-1, es);
      laz.assign(n*2-1, ef);
      copy(v.begin(), v.end(), dat.begin()+n-1);
      build();
  }
  inline int chld(int k) {return k*2+1;}
  inline int chrd(int k) {return k*2+2;}
  void set(int i, S s) {dat[i+n-1] = s;}
  void build() {
    for(int k = n-2; k >= 0; k--) dat[k] = fx(dat[chld(k)], dat[chrd(k)]);
  }
  void eval(int k) {
    //if(laz[k] == ef) return;
    if(k < n-1) {
      laz[chld(k)] = ff(laz[chld(k)], laz[k]);
      laz[chrd(k)] = ff(laz[chrd(k)], laz[k]);
    }
    dat[k] = fa(dat[k], laz[k]);
    laz[k] = ef;
  }
  void update(int a, int b, F x, int k, int l, int r) {
    eval(k);
    if(a <= l and r <= b) {
      laz[k] = ff(laz[k], x);
      eval(k);
    }
    else if(a < r and l < b) {
      update(a, b, x, chld(k), l, (l+r)>>1);
      update(a, b, x, chrd(k), (l+r)>>1, r);
      dat[k] = fx(dat[chld(k)], dat[chrd(k)]);
    }
  }
  void update(int a, int b, F x) {update(a, b, x, 0, 0, n);}
  S query(int a, int b, int k, int l, int r) {
    eval(k);
    if(r <= a or b <= l) return es;
    else if(a <= l and r <= b) return dat[k];
    else {
      S vl = query(a, b, chld(k), l, (l+r)>>1);
      S vr = query(a, b, chrd(k), (l+r)>>1, r);
      return fx(vl, vr);
    }
  }
  S query(int a, int b) {return query(a, b, 0, 0, n);}
  template<class G>
  int max_right(int l, G g) {
    assert(g(es));
    if(l == _n) return _n;
    l += n;
    for(int i = log; i >= 0; i--) eval((l>>i)-1);
    S now = es;
    do{
      while(~l&1) l >>= 1;
      if(!g(fx(now, dat[l-1]))) {
        while(l < n) {
          eval(l-1);
          l <<= 1;
          if(g(fx(now, dat[l-1]))) {
            now = fx(now, dat[l++ - 1]);
          }
        }
        return l-n;
      }
      now = fx(now, dat[l++ - 1]);
    } while((l & -l) != l);
    return _n;
  }
  template<class G>
  int min_left(int r, G g) {
    assert(g(es));
    if(r == 0) return 0;
    r += n;
    for(int i = log; i >= 0; i--) eval(((r-1)>>i)-1);
    S now = es;
    do{
      r--;
      while(r > 1 and (r&1)) r >>= 1;
      if(!g(fx(dat[r-1], now))) {
        while(r < n) {
          eval(r-1);
          r = chld(r);
          if(g(fx(dat[r-1], now))) {
            now = fx(dat[--r], now);
          }
        }
        return r+1-n;
      }
      now = fx(dat[r-1], now);
    } while((r & -r) != r);
    return 0;
  }
  //debug
  inline const S operator[](const int i) {return query(i, i+1);}
  void print() {for(int i = 0; i < n; i++) cout << (*this)[i] << (i == n-1?'\n':' ');}
};

//const unsigned int mod = 1000000007;
const unsigned int mod = 998244353;

struct mint {
  unsigned int x;
  mint():x(0) {}
  mint(int64_t x_) {
    int64_t v = int64_t(x_ % mod);
    if(v < 0) v += mod;
    x = (unsigned int)v;
  }
  static mint row(int v) {
    mint v_;
    v_.x = v;
    return v_;
  }
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    uint64_t z = x;
    z *= a.x;
    x = (unsigned int)(z % mod);
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  friend bool operator==(const mint &a, const mint &b) {return a.x == b.x;}
  friend bool operator!=(const mint &a, const mint &b) {return a.x != b.x;}
  mint &operator++() {
    x++;
    if(x == mod) x = 0;
    return *this;
  }
  mint &operator--() {
    if(x == 0) x = mod;
    x--;
    return *this;
  }
  mint operator++(int) {
    mint result = *this;
    ++*this;
    return result;
  }
  mint operator--(int) {
    mint result = *this;
    --*this;
    return result;
  }
  mint pow(int64_t t) const {
    mint x_ = *this, r = 1;
    while(t) {
      if(t&1) r *= x_;
      x_ *= x_;
      t >>= 1;
    }
    return r;
  }
  //for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) {return mint(*this) /= a;}
};

istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

//head

struct S {
  mint val;
  int siz;
};
struct F {
  mint a, b;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<S> a(n);
  rep(i, n) cin >> a[i].val, a[i].siz = 1;
  SegTreeL<S, F> seg(a, [](S a, S b)->S{return S{a.val+b.val, a.siz+b.siz};}, [](S a, F b)->S{return S{a.val*b.a + b.b*a.siz, a.siz};}, [](F a, F b)->F{return F{a.a*b.a, b.a*a.b+b.b};}, (S){mint(), 0}, (F){mint(1), mint()});
  while(q--) {
    int type, l, r;
    cin >> type >> l >> r;
    if(type) {
      cout << seg.query(l, r).val << '\n';
    }
    else {
      mint b, c;
      cin >> b >> c;
      seg.update(l, r, {b, c});
    }
  }
}