RT，分块第十个点 TLE，求调

#include<bits/stdc++.h>
#define N 300010
#define LL long long
#define ULL unsigned long long
#define DB double
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define tep(i,u) for(int i=head[u];~i;i=E[i].nxt)
#define INF 0x3f3f3f3f
#define mod 1000000009
using namespace std;
template <typename T> inline void read(T &a)
{
	a=0;T w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+(ch^48);ch=getchar();}
	a*=w;
}
template <typename T,typename ...Args> inline
void read(T &x,Args &...args){read(x);read(args...);}
int n,m,belong[N],bl[N],br[N],blen;
int a[N],f[N],pref[N],add1[N],add2[N],sum[N];
signed main()
{
	read(n);read(m);f[1]=f[2]=1;
	rep(i,3,n) f[i]=(1ll*f[i-1]+f[i-2])%mod;
	rep(i,1,n) read(a[i]),pref[i]=(1ll*f[i]+pref[i-1])%mod;
	blen=sqrt(n);
	rep(i,1,n)
	{
		belong[i]=(i-1)/blen+1;
		if(!bl[belong[i]]) bl[belong[i]]=i,br[belong[i]-1]=i-1;
		(sum[belong[i]]+=1ll*a[i])%=mod;
	}
	br[belong[n]]=n;
	while(m--)
	{
		int opt,l,r;read(opt,l,r);
		if(opt==1)
		{
			if(belong[l]^belong[r])
			{
				rep(i,l,br[belong[l]])
				{
					(a[i]+=1ll*f[i-l+1])%=mod;
					(sum[belong[i]]+=1ll*f[i-l+1])%=mod;
				}
				rep(i,belong[l]+1,belong[r]-1) 
				{
					(add1[i]+=1ll*f[bl[i]-l-1])%=mod;
					(add2[i]+=1ll*f[bl[i]-l  ])%=mod;
				}
				rep(i,bl[belong[r]],r)
				{
					(a[i]+=1ll*f[i-l+1])%=mod;
					(sum[belong[i]]+=1ll*f[i-l+1])%=mod;
				}
			}
			else
			{
				rep(i,l,r)
				{
					(a[i]+=1ll*f[i-l+1])%=mod;
					(sum[belong[i]]+=1ll*f[i-l+1])%=mod;
				}
			}
		}
		else if(opt==2)
		{
			LL ans=0;
			if(belong[l]^belong[r])
			{
				rep(i,l,br[belong[l]])
				{
					int b=belong[i];
					(ans+=1ll*((a[i]+1ll*add1[b]*f[i-bl[b]+1]%mod)%mod+1ll*add2[b]*f[i-bl[b]+2]%mod)%mod)%=mod;
				}
				rep(i,belong[l]+1,belong[r]-1)
				{
					int len=br[i]-bl[i]+1;
					(ans+=1ll*((sum[i]+1ll*add1[i]*pref[len]%mod)%mod+1ll*add2[i]*(pref[len+1]-1)%mod)%mod)%=mod;
				}
				rep(i,bl[belong[r]],r)
				{
					int b=belong[i];
					(ans+=1ll*((a[i]+1ll*add1[b]*f[i-bl[b]+1]%mod)%mod+1ll*add2[b]*f[i-bl[b]+2]%mod)%mod)%=mod;
				}
			}
			else
			{
				rep(i,l,r)
				{
					int b=belong[i];
					(ans+=1ll*((a[i]+1ll*add1[b]*f[i-bl[b]+1]%mod)%mod+1ll*add2[b]*f[i-bl[b]+2]%mod)%mod)%=mod;
				}
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}