样例正确,自拟1k范围数据跟题解对拍,但全部RE,求助

#include<bits/stdc++.h>
#define LL a*2
#define RR a*2+1
#define llee (t[a].r-t[a].l+1)
using namespace std;
long long Chs[50010][23]= {{1},{1,1},{1,2,1}};
int l,r,mm,n,k,mo=19940417,ip[50010];
long long ls[22];
char pp;
long long m(long long m) {
	return (m%mo+mo)%mo;
}
struct p {
	int l,r,len,flz,alz;
	long long ans[22];
} t[400106];
void mod(int a) {
	t[a].alz=m(t[a].alz);
	for(int i=1; i<21; i++)t[a].ans[i]=m(t[a].ans[i]);
}
void xa(int a,int k) {
	long long qarr[22]= {1,k};
	for(int i=2; i<=22; i++)qarr[i]=m(qarr[i-1]*k);
	for(int i=t[a].len; i>=1; i--) {
		for(int j=0; j<i; j++) {
			t[a].ans[i]+=m(t[a].ans[j]*qarr[i-j])*Chs[llee-j][i-j];
			t[a].ans[i]=m(t[a].ans[i]);
		}
	}
}
void pup(int a) {
	for(int i=1; i<21; i++)t[a].ans[i]=0;
	for(int i=1; i<21; i++) {
		for(int j=0; j<=i; j++) {
			t[a].ans[i]+=t[LL].ans[j]*t[RR].ans[i-j];
			t[a].ans[i]=m(t[a].ans[i]);
		}
	}
	return;
}
void ass(int a) {
	long long lss[22];
	for(int i=0; i<21; i++)lss[i]=ls[i];
	for(int i=1; i<21; i++)ls[i]=0;
	for(int i=1; i<21; i++) {
		for(int j=0; j<=i; j++) {
			ls[i]+=(t[a].ans[j]*lss[i-j])%mo;
			ls[i]=m(ls[i]);
		}
	}
	return;
}
void pd(int a) {
	if(t[a].l==t[a].r) {
		t[a].alz=0;
		t[a].flz=1;
		return;
	}
	if(t[a].flz==-1) {
		t[LL].flz*=-1;
		t[RR].flz*=-1;
		t[LL].alz=(mo-t[LL].alz)%mo;
		t[RR].alz=(mo-t[RR].alz)%mo;
		for(int i=1; i<21; i+=2) {
			t[LL].ans[i]=mo-t[LL].ans[i];
			t[RR].ans[i]=mo-t[RR].ans[i];
		}
	}
	if(t[a].alz!=0) {
		t[LL].alz+=t[a].alz;
		t[RR].alz+=t[a].alz;
		xa(LL,t[a].alz);
		xa(RR,t[a].alz);
	}
	t[a].alz=0;
	t[a].flz=1;
	mod(LL);
	mod(RR);
}
void add(int a) {
	if(l<=t[a].l&&t[a].r<=r) {
		t[a].alz+=k;
		xa(a,k);
		mod(a);
		return;
	}
	pd(a);
	if(t[LL].r>=l)add(LL);
	if(t[RR].l<=r)add(RR);
	pup(a);
	mod(a);
	return;
}
void qf(int a) {
	if(l<=t[a].l&&t[a].r<=r) {
		t[a].flz*=-1;
		t[a].alz=(mo-t[a].alz)%mo;
		for(int i=1; i<21; i+=2) {
			t[a].ans[i]=(mo-t[a].ans[i])%mo;
		}
		return;
	}
	pd(a);
	if(t[LL].r>=l)qf(LL);
	if(t[RR].l<=r)qf(RR);
	pup(a);
	mod(a);
	return;
}
void sc (int a) {
	if(l<=t[a].l&&t[a].r<=r) {
		ass(a);
		return;
	}
	pd(a);
	if(t[LL].r>=l)sc(LL);
	if(t[RR].l<=r)sc(RR);
	return;
}
void bd(int a,int l,int r) {
	t[a].l=l;
	t[a].r=r;
	t[a].len=min(r-l+1,20);
	t[a].alz=0;
	t[a].flz=1;
	for(int i=1; i<21; i++) {
		t[a].ans[i]=0;
	}
	t[a].ans[0]=1;
	if(l==r) {
		t[a].ans[1]=m(ip[l]);
		return;
	}
	int mid=((l+r)>>1);
	bd(LL,l,mid);
	bd(RR,mid+1,r);
	pup(a);
	return;
}
int main() {
	cin>>n>>mm;
	for(int i=1; i<=n; i++) {
		cin>>ip[i];
	}
	bd(1,1,n);
	
	for(int i=1; i<=mm; i++) {
		cin>>pp>>l>>r;
		if(pp=='I') {
			cin>>k;
			add(1);
		} else if(pp=='Q') {
			cin>>k;
			for(int i=1; i<21; i++)ls[i]=0;
			ls[0]=1;
			sc(1);
			cout<<ls[k]<<endl;
		} else {
			qf(1);
		}
//		for(int i=1; i<21; i++)printf("%lld ",t[1].ans[i]);
//		printf("\n");
	}
	return 0; 
}