#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110000;
const int M = 110000;
int n, m1, m=0, q1=0, jia[N], kq=1, ka=1, ans[M], p, time=0;
long long ans1=0, s[N];
struct attack{
	int t, x, d;
}a[M];
struct que{
	int t, x, id;
}q[M];
bool cmpa(attack a, attack b){
	if(a.x<b.x) return true;
	if(a.t<b.t && a.x==b.x) return true;
	return false;
}
bool cmpq(que a, que b){
	if(a.x<b.x) return true;
	if(a.t<b.t && a.x==b.x) return true;
	return false; 
}
void add(int x, int y){
	while(x<=n){
		s[x]+=y;
		x = x+(x&(-x));
	}
}
long long check1(int x){
	long long s1 = 0;
	while(x>0){
		s1+=s[x];
		x = x-(x&(-x));
	}
	return s1;
}
int check(int x){
	int l=0, r=time;
	while(l<r){
		int mid = (l+r)/2;
		if(s[mid-1]<jia[x] && s[mid]>=jia[x]) return mid;
		if(s[mid]>=jia[x]) r = mid;
		else l = mid+1;
	}
	return l;
}
long long find1(int x){
	if(x>p)	return check1(x)*2-check1(p);
	else return check1(x);
}
int num=0; 
char ch;
int main(){
	freopen("ex1.in", "r", stdin);
	scanf("%d%d", &n, &m1);
	for(int i=1;i<=n;i++) scanf("%d", &jia[i]);
	for(int i=1;i<=m1;i++){
		scanf("\n%c", &ch);
		if(ch=='A'){
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
//			printf("%d %d %d\n", i, m, a[1].x);
			time++;
			a[++m].d = z; a[m].t = time; a[m].x = x;
			a[++m].d = -z;a[m].t = time; a[m].x = y+1;
		}
		if(ch=='Q'){
			int x;
			scanf("%d", &x);
			q[++q1].t = time; q[q1].x=x; q[q1].id=++num;
		}
	}
	sort(a+1, a+m+1, cmpa);
	sort(q+1, q+q1+1, cmpq);
	memset(s, 0, sizeof(s));
	for(int i=1;i<=n;i++){
		while(ka<=m&&a[ka].x==i){
			add(a[ka].t, a[ka].d);
			ka++;
		}
		p=check(i);
//		printf("i= %d %d   ", i, p);
//		printf("%d %d %d  ", a[ka].t, a[ka].d, a[ka].x);
//		for(int j=1;j<=4;j++) printf("%d ", check1(j));
//		printf("\n");
		while(kq<=q1&&q[kq].x==i){
//			printf("ss %d %d\n", i, q[kq].t);
//			if(find1(q[kq].t, i)<0) printf("d");
			ans1+=find1(q[kq].t);
			ans1%=1000000009;
//			printf("dd %d %d\n", i, ans[q[kq].id]);
			ans[q[kq].id]=find1(q[kq].t);
			kq++;
		}
	}
	for(int i=1;i<=5;i++) printf("%d ",ans[i]);
	printf("\n");
	for(int i=1;i<=5;i++) printf("%d ",ans[i+5]);
	printf("\n");
	for(int i=1;i<=5;i++) printf("%d ",ans[i+10]);
	printf("\n");
	printf("%lld\n", ans1);	
}