In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation 

F1 = 1; F2 = 1; Fn = Fn - 1 + Fn - 2 (n > 2).

DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of n integers: a1, a2, ..., an. Moreover, there are m queries, each query has one of the two types:

  1. Format of the query "1 l r". In reply to the query, you need to add Fi - l + 1 to each element ai, where l ≤ i ≤ r. 
  2. Format of the query "2 l r". In reply to the query you should output the value of <image> modulo 1000000009 (109 + 9). 



Help DZY reply to all the queries.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 300000). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — initial array a.

Then, m lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality 1 ≤ l ≤ r ≤ n holds.

Output

For each query of the second type, print the value of the sum on a single line.

Examples

Input

4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3


Output

17
12

Note

After the first query, a = [2, 3, 5, 7].

For the second query, sum = 2 + 3 + 5 + 7 = 17.

After the third query, a = [2, 4, 6, 9].

For the fourth query, sum = 2 + 4 + 6 = 12.
import java.io.*;
import java.util.*;


public class Main {

	static final int MAX = 300009;
	static int fibonacciArray[];
	static int sum[];
	static final int MOD = 1000000009; 
	static int[] array ;
	static int[][] shifter;
	static int[][] A,S;
	
	public static void main( String args[])
	{
	MyScanner sc = new MyScanner();
	MyWriter mw = new MyWriter();
	
	int n= sc.nextInt();
	int q = sc.nextInt();
	
	array = new int[n+1];	
	
	initialiseArrays();
	
	for( int i = 1 ; i <= n ;++i )
		array[i] = sc.nextInt();
	
		SegTree tree = new SegTree( array );
	
	int t , l , r ; 
	
	
	//for( int i = 0 ; i < 9 ; ++i )
		//System.out.println( "index " + i + " has value = " + tree.tree[i].value + " and " + tree.tree[i].needsUpdation );
	
	
	while( q-- > 0 )
	{
		
		t = sc.nextInt();
		l = sc.nextInt();
		r = sc.nextInt();
		
		if( t == 1)
			tree.updateRange(l,r);
		
		else
			{
			mw.println( tree.queryRange(0 , l, r) + "");
			}
		
	//	for( int i = 0 ; i < 9 ; ++i )
			//System.out.println( "index " + i + " has value = " + tree.tree[i].value + " and " + tree.tree[i].needsUpdation );
		
	}
	
	mw.close();
	
	}
	
	static void initialiseArrays()
	{
		
		shifter = new int[][]{
				{0,1,0},
				{1,1,0},
				{1,1,1}
			};
		
		
		A = new int[MAX][2];
		S = new int[MAX][2];
		
		A[1] = new int[]{1,0};
		S[1]= new int[]{1,0};
		S[2] = new int[]{1,1};
		
		int[][] temp = new int[][]{
									{1,0},
									{0,1},
									{1,1}
								};
		
		for( int i = 2 ; i < MAX - 1  ; ++i )
		{
			temp = multiply( shifter , temp );
			A[i][0] = temp[0][0];
			A[i][1] = temp[0][1];
			
			S[i+1][0] = temp[2][0];
			S[i+1][1] = temp[2][1];
		}
	}
	
	static class SegTree {
		
		node tree[];
		int array[] ; 

		public SegTree(int array[])
	 	{
			tree = new node[ 6*array.length +2];
			for( int i = 0 ; i < 6*array.length + 2 ; ++i)
				tree[i] = new node();
			this.array = array ; 
			spreadDownwards( 0 , 0 , array.length - 1 );
		}
		
		 void updateRange( int l , int r  )
		{
			
			updateIndividually( 0 , l , r , 1 , 1 );
			
		}
		
		int queryRange(int index , int l , int r )
		{
			long ans = 0 ; 
			
			node t = tree[index];
			
			if( r < t.l || t.r < l )
				ans = 0 ;
			
			else if( l <= t.l && t.r <= r )
				ans =  tree[index].value;
			// now the partition occurs
			
			else  
			{
				split(index);
				ans = queryRange( index*2+1 , l , r );
				ans += queryRange( index*2+2 , l , r );
				// now handle it 
			}
				
				
			return (int)(ans%MOD);
		}
		
		 void updateIndividually( int index , int l , int r , int a , int b )
		{
			 node t = tree[index] ; 
			
			if( t.l == l && t.r == r )
			{
				t.a = (int)((t.a + a)%MOD);
				t.b = (int)((t.b + b)%MOD);
				
				tree[index].needsUpdation = true; 
			}
			
			else 
			{
				int mid = (t.l + t.r )/2;
				
				if( mid < l )
				{
					//update right one
					updateIndividually(2*index+2 ,l, r,a,b);
				}
				
				else if( r <= mid )
				{
					//left one
					updateIndividually(2*index+1 ,l, r,a,b);
				}
				
				else 
				{
					//parition
					int offset = mid - l + 1 ; 
					updateIndividually(2*index+1 ,l, mid,  a,b );
					updateIndividually(2*index+2 , mid+1 , r ,   getA( a,b,offset) ,  getB( a,b,offset) );
				}
			}
			
			long delta = getSum(a,b,r-l+1);
			//System.out.println( delta + " = (" + a + "," +  b + "," + (r-l+1) + ")to be added to " +  index);
			tree[index].value =  (int)((t.value + delta)%MOD) ; //  update anyhow
		}
		
		int getA(int a , int b , int n )
		{
			n++;
			long ans = 0 ; 
			ans +=  (long)a*A[n][0];
			ans +=  (long)b*A[n][1];
			
			//System.out.println( "A(" + a + "," + b + "," + n + ") = " + ans );
			return (int)(ans%MOD);
			
		}
		
		int getB(int a , int b , int n )
		{
			n++;
			long ans = 0 ; 
			ans += (long)a*A[n+1][0];
			ans += (long)b*A[n+1][1];
			
			return (int)(ans%MOD);
		}
		
		int getSum(int a , int b , int n )
		{
			long ans = 0 ; 
			ans +=  (long)a*S[n][0];
			ans +=  (long)b*S[n][1];
			
			return (int)(ans%MOD);
			
		}

		void spreadDownwards( int index , int first , int last )
		{

			node t = tree[index];
			t.needsUpdation = false;
			
			if( first == last )
			{
				t.value =  array[ first ];
				t.l = t.r = first ; 
			}
			
			else 
			{
				
				int mid = (first + last )/2;
				t.l = first;
				t.r = last;
				spreadDownwards( index*2+1 , first , mid );
				spreadDownwards( index*2+2 , mid+1 , last );
				 t.value = (int)((tree[index*2 + 1].value + (long)tree[index*2 + 2].value)%MOD); 
			}
		}
			

		void split( int index )
		{
		
			node t = tree[index];
			
			if( !t.needsUpdation ) return ; 
			
			int mid = ( t.l + t.r )/2 ;  
			int offset = mid - t.l + 1 ; 	
			
			int newA = getA(t.a,t.b,offset);
			int newB = getB(t.a,t.b,offset);
			
			
			updateIndividually(index*2+1,t.l,mid,t.a,t.b);
			updateIndividually(index*2+2,mid+1,t.r,newA,newB);
			
			tree[index].needsUpdation = false;
			tree[index].a = 0 ; 
			tree[index].b = 0 ; 
		}
			
	}
	
	static class node
	{
		boolean needsUpdation = false;
		int l, r ; 
		int a , b ; 
		int value ;

	}
	
	static int[][] multiply( int[][]  l , int[][] r )
	{
		int n , k , m ;
		n = l.length;
		k = l[0].length; 
		m = r[0].length;
		
		int[][] result = new int[n][m];
		
		for( int i = 0 ; i < n ; ++i)
			for( int j = 0 ; j < m ; ++j )
			{
				long temp = 0 ;
				
				for( int z = 0 ; z < k ; ++z)
				{
					temp = ( temp + ((long)l[i][z])*r[z][j])%MOD;
				}
				
				result[i][j] = (int )(temp);
				
			}
	
		
		return result ; 
	}
	

	static class MyScanner 
{
	      BufferedReader br;
	      StringTokenizer st;
	 
	      public MyScanner() {
	         br = new BufferedReader(new InputStreamReader(System.in),8*1024);
	      }
	 
	      String next() {
	          while (st == null || !st.hasMoreElements()) {
	              try {
	                  st = new StringTokenizer(br.readLine());
	              } catch (IOException e) {
	                  e.printStackTrace();
	              }
	          }
	          return st.nextToken();
	      }
	 
	      int nextInt() {
	          return Integer.parseInt(next());
	      }
	 
	      long nextLong() {
	          return Long.parseLong(next());
	      }
	 
	      double nextDouble() {
	          return Double.parseDouble(next());
	      }
	 
	      String nextLine(){
	          String str = "";
		  try {
		     str = br.readLine();
		  } catch (IOException e) {
		     e.printStackTrace();
		  }
		  return str;
	      }

	   }

	static class MyWriter 
{
	    BufferedWriter bw;

	    public  MyWriter() {
	       bw = new BufferedWriter(new OutputStreamWriter(System.out),8*1024);
	    }

	    void print(String s)
	    {
	    	
	    }
	    
	    void println(String s)
	    {
	    	try {
				bw.write( s , 0 , s.length() );
				bw.newLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
	    }

	 void close()
	 {
		 try {
			bw.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	 }
	}

}
