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.
//package codeforces;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

public class E {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter writer = new PrintWriter(System.out);
    StringTokenizer stringTokenizer;

    String next() throws IOException {
        while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
            stringTokenizer = new StringTokenizer(reader.readLine());
        }
        return stringTokenizer.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    final int MOD = 1000 * 1000 * 1000 + 9;

    int sum(int a, int b) {
        a += b;
        return a >= MOD ? a - MOD : a;
    }

    int product(int a, int b) {
        return (int) (1l * a * b % MOD);
    }

    @SuppressWarnings("unchecked")
    void solve() throws IOException {
        final int n = nextInt();
        final int[][][] fibonacciMatrices = new int[n + 1][2][2];
        fibonacciMatrices[0] = new int[][]{{1, 0}, {0, 1}};
        int[][] fm = {{1, 1}, {1, 0}};
        for(int r = 1; r <= n; r++) {
            for(int i = 0; i < 2; i++) {
                for(int j = 0; j < 2; j++) {
                    for(int k = 0; k < 2; k++) {
                        fibonacciMatrices[r][i][j] = sum(fibonacciMatrices[r][i][j], product(fibonacciMatrices[r - 1][i][k], fm[k][j]));
                    }
                }
            }
        }
        final int[][] howMuch = new int[n + 1][2];
        howMuch[0][0] = howMuch[1][1] = 1;
        for(int i = 2; i <= n; i++) {
            for(int k = 0; k < 2; k++) {
                howMuch[i][k] = sum(howMuch[i - 1][k], howMuch[i - 2][k]);
            }
        }
        final int[][] sum = new int[n + 1][2];
        for(int i = 1; i <= n; i++) {
            for(int k = 0; k < 2; k++) {
                sum[i][k] = sum(sum[i - 1][k], howMuch[i][k]);
            }
        }
        class SegmentTree {
            int q = 1; {
                while(q <= n) {
                    q *= 2;
                }
            }
            int[][] a = new int[2 * q][2];
            int[] s = new int[2 * q];

            int fibSum(int len, int a0, int a1) {
                int result = 0;
                int[] a01 = {a0, a1};
                for(int k = 0; k < 2; k++) {
                    result = sum(result, product(a01[k], sum[len][k]));
                }
                return result;
            }

            void add(int from, int to, int a0, int a1, int seg, int l, int r) {
                s[seg] = sum(s[seg], fibSum(to - from, a0, a1));
                if(from == l && to == r) {
                    a[seg][0] = sum(a[seg][0], a0);
                    a[seg][1] = sum(a[seg][1], a1);
                    return;
                }
                int med = l + r >> 1;
                if(a[seg][0] != 0 || a[seg][1] != 0) {
                    propagate(seg, l, r);
                }
                if(to <= med) {
                    add(from, to, a0, a1, seg * 2, l, med);
                    return;
                }
                if(from >= med) {
                    add(from, to, a0, a1, seg * 2 + 1, med, r);
                    return;
                }
                add(from, med, a0, a1, seg * 2, l, med);
                int[][] fm = fibonacciMatrices[med - from];
                add(med, to,
                        sum(product(fm[1][0], a1), product(fm[1][1], a0)),
                        sum(product(fm[0][0], a1), product(fm[0][1], a0)), seg * 2 + 1, med, r);
            }

            private void propagate(int seg, int l, int r) {
                int med = l + r >> 1;
                add(l, med, a[seg][0], a[seg][1], 2 * seg, l, med);
                int[][] fm = fibonacciMatrices[med - l];
                add(med, r,
                        sum(product(fm[1][0], a[seg][1]), product(fm[1][1], a[seg][0])),
                        sum(product(fm[0][0], a[seg][1]), product(fm[0][1], a[seg][0])), 2 * seg + 1, med, r);
                for(int k = 0; k < 2; k++) {
                    a[seg][k] = 0;
                }
            }

            int getSum(int from, int to, int seg, int l, int r) {
                if(from == l && to == r) {
                    return s[seg];
                }
                if(a[seg][0] != 0 || a[seg][1] != 0) {
                    propagate(seg, l, r);
                }
                int med = l + r >> 1;
                int res = 0;
                if(from < med) {
                    res = sum(res, getSum(from, Math.min(to, med), seg * 2, l, med));
                }
                if(to > med) {
                    res = sum(res, getSum(Math.max(from, med), to, seg * 2 + 1, med, r));
                }
                return res;
            }

            int getSum(int from, int to) {
                return getSum(from, to, 1, 0, q);
            }

            void add(int from, int to) {
                add(from, to, 0, 1, 1, 0, q);
            }
        }
        int[] a = new int[n];
        int[] ps = new int[n + 1];
        int m = nextInt();
        for(int i = 0; i < n; i++) {
            a[i] = nextInt();
            ps[i + 1] = sum(ps[i], a[i]);
        }
        SegmentTree segmentTree = new SegmentTree();
        for(int k = 0; k < m; k++) {
            int t = nextInt(), l = nextInt(), r = nextInt();
            if(t == 1) {
                segmentTree.add(l - 1, r);
            }
            if(t == 2) {
                int result = sum(sum(ps[r], MOD - ps[l - 1]), segmentTree.getSum(l - 1, r));
                writer.println(result);
            }
        }
        writer.close();
    }

    public static void main(String[] args) throws IOException {
        new E().solve();
    }
}


