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<bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)
 
const ULL M = 998244353;

struct RQ {
 using RQV = ULL;
 struct RQRV{ ULL b,c; };
 static RQV Zero(){ return 0; }
 static RQRV RZero(){ return { 1,0 }; }
 // addition
 static RQV f(RQV a,RQV b){ return (a+b) % M; }
 // update function
 static void uf(RQV& a,RQV b){ a = b; }
 // effect of range queries n-sized
 static void ef(RQV& a,RQRV b,int n){ a = (b.b*a + b.c*n) % M; }
 // range query update
 static void ruf(RQRV& a,RQRV b){
  a.b = (a.b * b.b) % M; 
  a.c = (a.c * b.b + b.c) % M;
 }
 // comparation
 static bool cmp(RQV l,RQV r){ return l<=r; }
 struct Node{
  RQV v; RQRV r;
 };
 int N;
 vector<Node> V;

 void init(int n){
  N=1; while (N<n) N*=2;
  V.assign(N*2,{Zero(),RZero()});
 }

 void spread(int i,int z){
  ef(V[i].v,V[i].r,z);
  if (z!=1) {
   ruf(V[i*2].r,V[i].r);
   ruf(V[i*2+1].r,V[i].r);
  }
  V[i].r = RZero();
 }

 void upd(int p,RQV v){
  for(int d=N; d>=1; d/=2) spread(p/d,d);
  p+=N; uf(V[p].v,v);
  int z=1;
  while(p!=1){
   p/=2; z*=2;
   V[p].v = f(V[p*2].v,V[p*2+1].v);
   ef(V[p].v,V[p].r,z);
  }
 }

 void updr(int l,int r,RQRV v,int a=0,int b=0,int i=-1){
  if(i==-1){ a=0; b=N; i=1; }
  if(r<=a || b<=l){ spread(i,b-a); return; }
  else if(l<=a && b<=r){ ruf(V[i].r,v); spread(i,b-a); return; }
  spread(i,b-a);
  updr(l,r,v,a,(a+b)/2,i*2);
  updr(l,r,v,(a+b)/2,b,i*2+1);
  V[i].v = f(V[i*2].v,V[i*2+1].v);
 }

 RQV query(int l,int r,int a=0,int b=0,int i=-1){
  if(i==-1){ a=0; b=N; i=1; }
  if(r<=a || b<=l) return Zero();
  spread(i,b-a);
  if(l<=a && b<=r) return V[i].v;
  RQV q1 = query(l,r,a,(a+b)/2,i*2);
  RQV q2 = query(l,r,(a+b)/2,b,i*2+1);
  q1 = f(q1,q2);
  return q1;
 }

 int find(int l,RQV v,int a=0,int b=0,int i=-1){
  static RQV x;
  if(i==-1){ a=0; b=N; i=1; x=Zero(); }
  spread(i,b-a);
  if(b<=l) return N;
  if(l<=a && !cmp(v,f(x,V[i].v))){ x=f(x,V[i].v); return N; }
  if(b-a==1) return a;
  int q1 = find(l,v,a,(a+b)/2,i*2);
  if(q1!=N) return q1;
  return find(l,v,(a+b)/2,b,i*2+1);
 }
};

int N,Q;
RQ G;
 
int main(){
 scanf("%d%d",&N,&Q);
 G.init(N);
 rep(i,N){
  int a; scanf("%d",&a);
  G.upd(i,a);
 }
 rep(q,Q){
  int c; scanf("%d",&c);
  if(c==0){
   int l,r,b,c; scanf("%d%d%d%d",&l,&r,&b,&c);
   G.updr(l,r,{(ULL)b,(ULL)c});
  }
  if(c==1){
   int l,r; scanf("%d%d",&l,&r);
   printf("%llu\n",G.query(l,r));
  }
 }
 
 return 0;
}