#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int f=1,x=0;
	char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<1)+(x<<3)+(s^48);
		s=getchar();
	}
	return x*f;
}
const int N=1e5+5,M=1<<17,Mod=1e9+9;
int n,Q,tot,ans,now=1;
int p[N]; 
struct Node{
	int l,r,val,id;
}a[N];
vector<int>q[N];
priority_queue<pair<int,int>>que;
bool Cmp(Node x,Node y){
	return x.l<y.l;
}
namespace TREE{
	int tr[N<<2];
	void Update(int pos,int val){
		while(pos<=M){
			tr[pos]+=val;
			pos+=pos&-pos;
		}
	}
	int Query(int pos){
		int res=0;
		while(pos){
			res+=tr[pos];
			pos-=pos&-pos;
		}
		return res;
	}
	int Find(int val){
		int res=0,sum=0;
		for(int i=17;i>=0;i--)
			if(sum+tr[res+(1<<i)]<val){
				res+=(1<<i);
				sum+=tr[res];
			}
		return res;
	}
}
signed main(){
	n=read(); Q=read();
	for(int i=1;i<=n;i++) p[i]=read();
	for(int i=1;i<=Q;i++){
		char ch; cin>>ch;
		if(ch=='A'){
			tot++;
			a[tot].l=read();
			a[tot].r=read();
			a[tot].val=read();
			a[tot].id=tot;
		} 
		else{
			int x=read();
			q[x].push_back(tot);
		} 
	}
	sort(a+1,a+tot+1,Cmp);
	for(int i=1;i<=n;i++){
		while(a[now].l==i){
			TREE::Update(a[now].id,a[now].val);
			que.push({a[now].r,now});
			now++;
		}
		while(!que.empty()&&que.top().first<i){
			int pos=que.top().second;
			que.pop();
			TREE::Update(a[pos].id,-a[pos].val);
		}
		if(q[i].empty()) continue;
		int pos=TREE::Find(p[i])+1;
		for(int j=0;j<q[i].size();j++){
			int id=q[i][j];
			if(pos>=id) ans+=TREE::Query(id);
			else ans+=TREE::Query(id)*2-TREE::Query(pos);
			ans%=Mod;
		} 
	}
	cout<<ans;
	return 0;
}