#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[200005],block,t,pos[200005],st[2005],ed[2005],mx[2005],add[2005],mod=998244353,k;
void build(){
	block=(int)sqrt(n);
	t=n/block;
	if(n%block){
		t++;
	}
	for(int i=1;i<=t;i++){
		st[i]=(i-1)*block+1;
		ed[i]=i*block;
	}
	ed[t]=n;
	for(int i=1;i<=t;i++){
		for(int j=st[i];j<=ed[i];j++){
			mx[i]=max(mx[i],a[j]);
		}
	}
	for(int i=1;i<=n;i++){
		pos[i]=(i-1)/block+1;
	}
}
void update1(int l,int r){//开方
	int x=pos[l];
	int y=pos[r];
	if(x==y){
		if(mx[x]==1){
			return;
		}
		if(add[x]>=1){
			add[x]--;
			return;
		}
		for(int i=l;i<=r;i++){
			a[i]=(int)sqrt(a[i]);
		}
		mx[x]=0;
		for(int i=st[x];i<=ed[x];i++){
			mx[x]=max(mx[x],a[i]);
		}
		return;
	}
	else{
		if(mx[x]!=1){
			for(int i=l;i<=ed[x];i++){
				a[i]=(int)sqrt(a[i]);
			}
			mx[x]=0;
			for(int i=st[x];i<=ed[x];i++){
				mx[x]=max(mx[x],a[i]);
			}
		}
		if(mx[y]!=1){
			for(int i=st[y];i<=r;i++){
				a[i]=(int)sqrt(a[i]);
			}
			mx[y]=0;
			for(int i=st[y];i<=ed[y];i++){
				mx[y]=max(mx[y],a[i]);
			}
		}
		for(int i=x+1;i<=y-1;i++){
			if(add[i]>=1){
				add[i]--;
				continue;
			}
			if(mx[i]==1){
				continue;
			}
			mx[i]=0;
			for(int j=st[i];j<=ed[i];j++){
				a[j]=(int)sqrt(a[j]);
				mx[i]=max(mx[i],a[j]);
			}
		}
		return;
	}
}
void update2(int l,int r){//平方
	int x=pos[l];
	int y=pos[r];
	if(x==y){
		for(int i=l;i<=r;i++){
			a[i]=a[i]*a[i];
			mx[x]=max(mx[x],a[i]);
		}
		return;
	}
	else{
		for(int i=l;i<=ed[x];i++){
			a[i]=a[i]*a[i];
			mx[x]=max(mx[x],a[i]);
		}
		for(int i=st[y];i<=r;i++){
			a[i]=a[i]*a[i];
			mx[y]=max(mx[y],a[i]);
		}
		for(int i=x+1;i<=y-1;i++){
			add[i]++;
		}
		return;
	}
}
int qpow(int x,int y){
	int ans=1,p=x;
	while(y>0){
		if(y&1){
			ans=ans%mod*p%mod;
			ans%=mod;
		}
		y>>=1;
		p*=p%mod;
		p%=mod;
	}
	return ans;
}
int phi(int x,int y){
	int ans=1;
	int p=x;
	while(y>0){
		if(y&1){
			ans*=p%k;
			ans%=k;
		}
		p=p%k*p%k;
		p%=k;
		y>>=1;
	}
	return ans%k;
}
signed main()
{
	k=mod-1;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build();
	for(int i=1;i<=m;i++){
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1){
			update1(l,r);
		}
		else{
			update2(l,r);
		}
	}
	for(int i=1;i<=t;i++){
		if(!add[i]){
			continue;
		}
		int x=phi(2,add[i])+k;
		for(int j=st[i];j<=ed[i];j++){
			a[j]=qpow(a[j],x)%mod;
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=(a[i]%mod);
		sum%=mod;
	}
	cout<<sum;
	return 0;
}