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.*;

import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.fill;


public class Main{


    void run(){
        Locale.setDefault(Locale.US);
        boolean my;
        try {
            my = System.getProperty("MY_LOCAL") != null;
        } catch (Exception e) {
            my = false;
        }
        try{
            err = System.err;
            if( my ){
                sc  = new FastScanner(new BufferedReader(new FileReader("input.txt")));
//                sc  = new FastScanner(new BufferedReader(new FileReader("C:\\myTest.txt")));
                out = new PrintWriter   (new FileWriter("output.txt"));
            }
            else {
                sc  = new FastScanner( new BufferedReader(new InputStreamReader(System.in)) );
                out = new PrintWriter( new OutputStreamWriter(System.out));
            }
//            out = new PrintWriter(new OutputStreamWriter(System.out));
        }catch(Exception e){
            MLE();
        }
        if( my )
            tBeg = System.currentTimeMillis();
        solve();
        if( my )
            err.println( "TIME: " + (System.currentTimeMillis() - tBeg ) / 1e3 );
        exit(0);
    }

    void exit( int val ){
        err.flush();
        out.flush();
        System.exit(val);
    }

    double tBeg;
    FastScanner sc;
    PrintWriter out;
    PrintStream err;

    class FastScanner{

        StringTokenizer st;
        BufferedReader br;

        FastScanner( BufferedReader _br ){
            br = _br;
        }

        String readLine(){
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        String next(){
            while( st==null || !st.hasMoreElements() )
                st = new StringTokenizer(readLine());
            return st.nextToken();
        }

        int nextInt(){ return Integer.parseInt(next()); }
        long nextLong(){ return Long.parseLong(next()); }
        double nextDouble(){ return Double.parseDouble(next()); }
    }

    void MLE(){
        int[][] arr = new int[1024*1024][]; for( int i = 0; i < 1024*1024; ++i ) arr[i] = new int[1024*1024];
    }

    void MLE( boolean doNotMLE ){ if( !doNotMLE ) MLE(); }

    void TLE(){
        for(;;);
    }

    public static void main(String[] args) {
        new Main().run();
//        new Thread( null, new Runnable() {
//            @Override
//            public void run() {
//                new Main().run();
//            }
//        }, "Lolka", 256_000_000L ).run();
    }

    ////////////////////////////////////////////////////////////////

    final long mod = (int)1e9 + 9;
    int n, Q;
    long[] sumA;
    long[] sum, conQ, conP;

    //    final long sqrt5 = 383008016;
    final long sqrt5 = 616991993;
    final long inv2 = valueOf(2).modInverse(valueOf(mod)).intValue();
    final long q = (1+sqrt5    )*inv2 % mod;
    final long p = (1-sqrt5+mod)*inv2 % mod;
    final long coef = valueOf(sqrt5).modInverse(valueOf(mod)).intValue();
    final long[] sumPowQ = new long[300_001];
    final long[] sumPowP = new long[300_001];
    final long[] powQ = new long[300_001];
    final long[] powP = new long[300_001];
    final long[] invPowQ = new long[300_001];
    final long[] invPowP = new long[300_001];
    {
        powQ[1] = q;
        powP[1] = p;
        for (int i = 2; i < sumPowP.length; i++) {
            powQ[i] = powQ[i-1] * q % mod;
            powP[i] = powP[i-1] * p % mod;
        }
        for (int i = 1; i < sumPowP.length; i++) {
            sumPowQ[i] = add(powQ[i], sumPowQ[i-1]);
            sumPowP[i] = add(powP[i], sumPowP[i-1]);
            invPowP[i] = powInv(powP[i]);
            invPowQ[i] = powInv(powQ[i]);
        }
        invPowQ[0] = 1;
        invPowP[0] = 1;
    }

    long add( long a, long b ){
        long c = a + b;
        while( mod <= c ) c -= mod;
        while( c < 0 ) c += mod;
        return c;
    }

    long sub( long a, long b ){
        long c = a - b;
        while( mod <= c ) c -= mod;
        while( c < 0 ) c += mod;
        return c;
    }

    void solve(){
        n = sc.nextInt();
        Q = sc.nextInt();
        sumA = new long[n+1];
        for (int i = 1; i <= n; i++) {
            sumA[i] = (sumA[i-1] + sc.nextLong()) % mod;
        }

        for (int i = 1; i <= 7; i++)
            err.println( i +") "+ coef*( (sumPowQ[i]-sumPowQ[i-1]) - (sumPowP[i]-sumPowP[i-1]) + 4*mod )%mod );

        sum  = new long[8*(n+1)];
        conQ = new long[8*(n+1)]; fill( conQ, -1 );
        conP = new long[8*(n+1)]; fill( conP, -1);

        for (int iter = 0; iter < Q; iter++) {
            int op = sc.nextInt();
            int l = sc.nextInt();
            int r = sc.nextInt();
            if     ( op == 1 ){
                upd(l,r, l, 1,1,n);
            }
            else if( op == 2 ){
                long ans = getSum(l,r,1,1,n) + sumA[r] - sumA[l-1];
                ans = (ans%mod + mod)%mod;
                out.println( ans );
            }
            else MLE();
        }
        return;
    }

    private long getSum(int l, int r, int v, int tl, int tr) {
        if( l > r )
            return 0;
        if( l == tl && r == tr ){
            return sum[v];
        }
        else{
            int tm = (tl + tr)/2;
            long ans =
                add(
                    add(
                        getSum(              l, min(r,tm), 2*v  , tl  , tm ),
                        getSum( max(l, tm + 1),         r, 2*v+1, tm+1, tr )
                    ),
                    get(l,r, v,tl)
                );
            return ans;
        }
    }

    private void upd(int l, int r, int LQ, int v, int tl, int tr) {
        if( l > r )
            return;


        if( l == tl && r == tr ){
            if( conQ[v] == -1 ){
                conQ[v] = 0;
                conP[v] = 0;
            }
//            conQ[v] = add(conQ[v], powInv(powMod(q, LQ - 1)) );
//            conP[v] = add(conP[v], powInv(powMod(p, LQ - 1)) );
            conQ[v] = add(conQ[v], invPowQ[LQ-1] );
            conP[v] = add(conP[v], invPowP[LQ-1] );
        }
        else{
            int tm = (tl + tr)/2;
            upd(              l, min(r,tm), LQ, 2*v  , tl  , tm );
            upd( max(l, tm + 1),         r, LQ, 2*v+1, tm+1, tr );
        }
        sum[v] = add(add(sum[2*v], sum[2*v+1]), get(tl,tr, v,tl));
    }

    private long get(int l, int r, int v, int tl ) {
        long ans = 0;
        if( conQ[v] != -1 ){
            ans += coef * conQ[v] % mod * ( sumPowQ[r] - sumPowQ[l-1] ) % mod;
            ans -= coef * conP[v] % mod * ( sumPowP[r] - sumPowP[l-1] ) % mod;
            ans = ( ans%mod + mod ) % mod;
        }
        return ans;
    }

    private long powInv(long a) {
        return powMod( a, mod - 2 );
    }

    private long powMod(long a, long p) {
        if( p == 0 )
            return 1;
        long ans = powMod( a, p/2 );
        ans = ( ans * ans ) % mod;
        if( p%2 == 1 )
            ans = ( ans * a ) % mod;
        return ans;
    }
}
