#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<set>
using namespace std; 
typedef long long LL;
const int N=2e5+10,M=1e4+10,mod=998244353,inf=1e9+10,MOD=998244352;
int n,m,cnt,kuai,fa[N],l[M],r[M],b[N],lazy[M],c[N],vis[N],num[M];
LL a[N];
inline LL POW(LL a,int b){
	LL sum=1;
	for(;b;b>>=1,a=a*a%mod) if(b&1)sum=sum*a%mod;
	return sum;
}
inline void chonggou(int x){
	vis[x]=1;
	for(int i=l[x];i<=r[x];i++){
		b[i]+=lazy[x];
		if(a[i]!=1) vis[x]=0;
	}
	lazy[x]=0;
}
int main(){
	ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0); 
 	freopen("nzq.in","r",stdin);
 	freopen("nzq.out","w",stdout);
	cin>>n>>m; kuai=sqrt(n); c[0]=1;
	for(int i=1;i<=m;i++) c[i]=(c[i-1]<<1)%MOD;
	for(int i=1;i<=n;i++) fa[i]=i/kuai+1,cnt=fa[i];
	for(int i=1;i<=n;i++) r[fa[i]]=i;
	for(int i=n;i>=1;i--) l[fa[i]]=i;
	for(int i=1;i<=n;i++){ cin>>a[i];if(a[i]==1) num[fa[i]]++;}
	while(m--){
		int o,x,y;
		cin>>o>>x>>y;
		if(o==1){
			for(int i=fa[x];i<=fa[y];i++){
				if(vis[i]==1) continue;
				if(x<=l[i]&&r[i]<=y){
					if(lazy[i]>0) lazy[i]--;
					else{
						vis[i]=1;
						for(int j=l[i];j<=r[i];j++){
							if(b[j]>0) b[j]--;
							else{
								if(a[j]!=1&&sqrt(a[j])==1) num[i]++;
								a[j]=sqrt(a[j]);
							}
							if(a[j]!=1) vis[i]=0;
							if(num[i]==r[i]-l[i]+1){vis[i]=1;continue;}
						}
					}
				}else{
					if(lazy[i]!=0)chonggou(i);
					if(vis[i]==1) continue;
					int L=max(l[i],x),R=min(r[i],y);
					for(int j=L;j<=R;j++){
						if(a[j]==1) continue;
						if(b[j]>0) b[j]--;
						else{
							a[j]=sqrt(a[j]);
							if(a[j]!=1&&sqrt(a[j])==1) num[i]++;
						}
						if(num[i]==r[i]-l[i]+1){vis[i]=1;continue;}
					}
				}
			}
		}else{
			for(int i=fa[x];i<=fa[y];i++){
				if(vis[i]==1) continue;
				if(x<=l[i]&&r[i]<=y){
					lazy[i]++;
				}else{
					if(lazy[i]!=0)chonggou(i);
					if(vis[i]==1) continue;
					int L=max(l[i],x),R=min(r[i],y);
					for(int j=L;j<=R;j++)b[j]++;
				}
			}
		}
	}
	LL ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]!=1)a[i]=POW(a[i],c[b[i]+lazy[fa[i]]]);
		ans+=a[i];
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}