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>
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 998244353;
constexpr long long inf = 3e18;

template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>
struct Segtree{
	int size=1;
	vector<Monoid>dat;
	vector<OperatorMonoid>lazy;
	const F f;
	const G g;
	const H h;
	Monoid M;
	OperatorMonoid OM;
	void set(int a,Monoid x){
		dat[a+size-1]=x;
	}
	void init(){
		for(int i=size-2;i>=0;i--){
			dat[i]=f(dat[i*2+1],dat[i*2+2]);
		}
	}
	void eval(int k,int l,int r){
		if(lazy[k]!=OM){
			dat[k]=g(dat[k],lazy[k],(r-l));
			if(r-l>1){
				lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
				lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
			}
			lazy[k]=OM;
		}
	}
	void update(int a,int b,OperatorMonoid M,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b){
			lazy[k]=h(lazy[k],M);
			eval(k,l,r);
			return;
		}
		update(a,b,M,k*2+1,l,(l+r)/2);
		update(a,b,M,k*2+2,(l+r)/2,r);
		dat[k]=f(dat[k*2+1],dat[k*2+2]);
	}
	Monoid query(int a,int b,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return M;
		if(a<=l&&r<=b)return dat[k];
		Monoid lv=query(a,b,k*2+1,l,(l+r)/2);
		Monoid rv=query(a,b,k*2+2,(l+r)/2,r);
		return f(lv,rv);
	}
	template<class C>
	int minLeft(int a,int b,C &check,Monoid x,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l||!check(dat[k],x))return -1;
		if(r-l==1)return l;
		int lv=minLeft(a,b,check,x,k*2+1,l,(l+r)/2);
		if(lv!=-1)return lv;
		return minLeft(a,b,check,x,k*2+2,(l+r)/2,r);
	}
	template<class C>
	int maxRight(int a,int b,C &check,Monoid x,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l||!check(dat[k],x))return -1;
		if(r-l==1)return l;
		int rv=maxRight(a,b,check,x,k*2+2,(l+r)/2,r);
		if(rv!=-1)return rv;
		return maxRight(a,b,check,x,k*2+1,l,(l+r)/2);
	}
	Segtree(int x,F f,G g,H h,Monoid M,OperatorMonoid OM)
	:f(f),g(g),h(h),M(M),OM(OM){
		while(size<x)size*=2;
		dat.resize(size*2-1,M);
		lazy.resize(size*2-1,OM);
	}
};
template<int MOD>
struct mint{
	int n;
	mint():n(0){}
	mint(int x):n(x>=0?x%MOD:(MOD-(-x)%MOD)%MOD){}

	mint &operator+=(const mint &p){
		if((n+=p.n)>=MOD)n-=MOD;
		return *this;
	}
	mint &operator-=(const mint &p){
		if((n+=MOD-p.n)>=MOD)n-=MOD;
		return *this;
	}
	mint &operator*=(const mint &p){
		n=n*p.n%MOD;
		return *this;
	}
	mint &operator/=(const mint &p){
		*this*=p.inverse();
		return *this;
	}
	mint operator-()const{return mint(-n);}
	mint operator+(const mint &p)const{return mint(*this)+=p;}
	mint operator-(const mint &p)const{return mint(*this)-=p;}
	mint operator*(const mint &p)const{return mint(*this)*=p;}
	mint operator/(const mint &p)const{return mint(*this)/=p;}
	bool operator==(const mint &p)const{return n==p.n;}
	bool operator!=(const mint &p)const{return n!=p.n;}

	friend ostream &operator<<(ostream &os,const mint &p){
		return os<<p.n;
	}
	friend istream &operator>>(istream &is,mint &p){
		int x;is>>x;
		p=mint(x);
		return is;
	}
	mint pow(int x)const{
		mint res(1),mul(n);
		while(x>0){
			if(x&1)res*=mul;
			mul*=mul;
			x>>=1;
		}
		return res;
	}
	mint inverse()const{
		return pow(MOD-2);
	}
};
using modint=mint<mod>;

using PM=pair<modint,modint>;
auto f=[](modint a,modint b)->modint{return a+b;};
auto g=[](modint a,PM b,int sz)->modint{return a*b.first+b.second*modint(sz);};
auto h=[](PM a,PM b)->PM{return PM(a.first*b.first,a.second*b.first+b.second);};
 
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	int N,Q;
	cin>>N>>Q;
	Segtree<modint,PM,decltype(f),decltype(g),decltype(h)>segtree(N,f,g,h,0,PM(1,0));
	rep(i,N){
		modint a;cin>>a;
		segtree.set(i,a);
	}
	segtree.init();
	while(Q--){
		int t;cin>>t;
		if(!t){
			int l,r;modint b,c;cin>>l>>r>>b>>c;
			segtree.update(l,r,PM(b,c));
		}else {
			int l,r;cin>>l>>r;
			cout<<segtree.query(l,r)<<"\n";
		}
	}
}