#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,G=3,GI=(mod+1)/3;
int qpow(int a,int b){
	int c=1;
	for(;b;b>>=1){
		if(b&1)c=1ll*a*c%mod;
		a=1ll*a*a%mod;
	}
	return c;
}
int lb[1<<20],L,wi[1<<20][2];
void init(int n){
	L=1;while(L<=n)L<<=1;
	for(int i=0;i<L;i++)lb[i]=(lb[i>>1]>>1)|((i&1)?(L>>1):0); 
}
void NTT(int *a,int fl){
	for(int i=0;i<L;i++)if(i<lb[i])swap(a[i],a[lb[i]]);
	for(int o=1;o<L;o<<=1){
		for(int i=0;i<L;i+=(o<<1))for(int j=0;j<o;j++){
			int x=a[i+j],y=1ll*wi[j+o][fl]*a[i+j+o]%mod;
			a[i+j]=(x+y)%mod,a[i+j+o]=(x-y)%mod;
		}
	}
	if(!fl){
		int I=qpow(L,mod-2);
		for(int i=0;i<L;i++)a[i]=1ll*a[i]*I%mod; 
	}
}
int se[201000],n,m,a[200100],p[201000],q[201000];
const int B=1000;
bool isi[200100];
int f[201000],z[201000];
int F[1<<20],Q[1<<20];
void build(){
	for(int i=0;i<L;i++)F[i]=0;
	//n-1-i i+j
	for(int i=0;i<n;i++)F[n-1-q[i]]++;
	NTT(F,1);for(int i=0;i<L;i++)F[i]=1ll*F[i]*Q[i]%mod;NTT(F,0);
	for(int i=0;i<n;i++)f[i]=F[n-1+i]; 
}
int main(){
	scanf("%d%d",&n,&m);init(n*4);
	for(int o=1;o<L;o<<=1){
		int p1=1,p2=1;
		int o1=qpow(G,(mod-1)/(o<<1)),o2=qpow(GI,(mod-1)/(o<<1));
		for(int j=0;j<o;j++){
			wi[o+j][0]=p1,wi[o+j][1]=p2;
			p1=1ll*p1*o2%mod,p2=1ll*p2*o1%mod;
		}
	}
	if(n&1){for(int i=0;i<=m;i++)puts("0");return 0;}
	for(int i=0;i<n;i++)scanf("%d",&se[i]),se[i+n]=se[i];
	for(int i=1;i<n*2;i++)(se[i]+=se[i-1])%=mod;
	for(int i=0;i<n;i++)a[i]=(se[i+n-n/4-1]-se[i+n/4])%mod;
	for(int i=0;i<n;i++)p[i]=q[i]=i;
	for(int i=0;i<n*2;i++)Q[i]=a[i%n];NTT(Q,1);
	build();printf("%d\n",f[0]);
	int dt=0;
	vector<int>xz;
	for(int i=1,oo,x,z;i<=m;i++){
		scanf("%d",&oo);
		if(oo==1){scanf("%d",&z);(dt+=z)%=n;}
		else{
			scanf("%d%d",&x,&z);(x+=n-dt)%=n;
			(p[x]+=n-z)%=n;
			if(!isi[x])isi[x]=1,xz.push_back(x);
		}
		int ans=f[dt];
		for(int o:xz)(ans-=a[(q[o]+dt)%n])%=mod,(ans+=a[(p[o]+dt)%n])%=mod;
		printf("%d\n",(ans+mod)%mod);
		if(xz.size()>=B){for(int j=0;j<n;j++)q[j]=p[j];for(int o:xz)isi[o]=0;xz.clear();build();}
	}
	return 0;
}