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.math.BigInteger;
import java.util.*;
import java.util.List;

public class Main {
    private static StringTokenizer st;
    private static BufferedReader br;
    public static long MOD = 1000000009;

    public static long[] fib;
    public static long[] fibPartial;

    public static void print(Object x) {
        System.out.println(x + "");
    }
    public static void printArr(long[] x) {
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < x.length; i++) {
            s.append(x[i] + " ");
        }
        print(s);
    }
    public static void printArr(int[] x) {
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < x.length; i++) {
            s.append(x[i] + " ");
        }
        print(s);
    }
    public static String join(Collection<?> x, String space) {
        if (x.size() == 0) return "";
        StringBuilder sb = new StringBuilder();
        boolean first = true;
        for (Object elt : x) {
            if (first) first = false;
            else sb.append(space);
            sb.append(elt);
        }
        return sb.toString();
    }

    public static String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            String line = br.readLine();
            st = new StringTokenizer(line.trim());
        }
        return st.nextToken();
    }
    public static int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public static long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public static List<Integer> nextInts(int N) throws IOException {
        List<Integer> ret = new ArrayList<Integer>();
        for (int i = 0; i < N; i++) {
            ret.add(nextInt());
        }
        return ret;
    }

    public static long advanceStart(long start, long inc, int k) {
        long startVal = (fib[k + 1] * start) % MOD;
        long incVal = (fib[k] * inc) % MOD;
        return (startVal + incVal) % MOD;
    }

    public static long advanceInc(long start, long inc, int k) {
        long cur = advanceStart(start, inc, k);
        long next = advanceStart(start, inc, k+1);
        return (next - cur + MOD) % MOD;
    }

    //Partial sum of length k elements.
    public static long partial(long start, long inc, int k) {
        if (k == 0) return 0;
        long total = fibPartial[k - 1] * inc;
        total += fibPartial[k] * start;
        return total % MOD;
    }

    public static class RangeTree {
        int size;
        RangeTree left;
        RangeTree right;
        //To be propagated
        long first;
        long increase;
        //Updated at receipt
        long sum;

        public RangeTree(int size) {
            this.size = size;
            if (size > 1) {
                left = new RangeTree(size / 2);
                right = new RangeTree(size - size / 2);
            }
        }

        //Lazily increments.
        public void increment(int l, int r, long start, long inc) {
            //update sum
            sum = (sum + partial(start, inc, r - l + 1)) % MOD;
            //print(l + " to " + r + " " + start + " " + inc + " val " + partial(start, inc, r - l + 1));

            //Increment children
            if (l == 0 && r == size - 1) {
                first = (first + start) % MOD;
                increase = (increase + inc) % MOD;
            }
            else if (r < left.size) left.increment(l, r, start, inc);
            else if (l >= left.size) right.increment(l - left.size, r - left.size, start, inc);
            else {
                left.increment(l, left.size - 1, start, inc);
                int k = size/2 - l;
                right.increment(0, r - left.size,
                        advanceStart(start, inc, k), advanceInc(start, inc, k));
            }
        }

        //Propagates stored value to children.
        public void propagate() {
            if (first == 0 & increase == 0) return;
            if (size == 1) return;
            left.increment(0, left.size - 1, first, increase);
            int k = size/2;
            right.increment(0, right.size - 1,
                    advanceStart(first, increase, k), advanceInc(first, increase, k));
            first = 0;
            increase = 0;
        }

        public long sum(int l, int r) {
            if (l == 0 && r == size - 1) return sum;

            propagate();
            if (r < left.size) return left.sum(l, r);
            else if (l >= left.size) return right.sum(l - left.size, r - left.size);
            else return (left.sum(l, left.size - 1) + right.sum(0, r - left.size)) % MOD;
        }
    }

    public static long[] cumulativeMod(long[] values) {
        int n = values.length;
        long cur = 0;
        long[] cumulative = new long[n];

        for (int i = 0; i < n; i++) {
            cur = (cur + values[i]) % MOD;
            cumulative[i] = cur;
        }
        return cumulative;
    }

    public static long[] fibMod(int n) {
        long[] values = new long[n];

        long last = 0;
        long cur = 1;
        for (int i = 1; i < n; i++) {
            values[i] = cur;
            long next = (last + cur) % MOD;
            last = cur;
            cur = next;
        }
        return values;
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        int n = nextInt();
        int m = nextInt();
        long[] nums = new long[n];
        for (int i = 0; i < n; i++) nums[i] = nextLong();
        long[] partialNums = cumulativeMod(nums);
        fib = fibMod(n + 10);
        fibPartial = cumulativeMod(fib);

        RangeTree t = new RangeTree(n);
        for (int i = 0; i < m; i++) {
            int type = nextInt();
            int l = nextInt() - 1;
            int r = nextInt() - 1;
            if (type == 1) {
                t.increment(l, r, 1, 0);
            } else {
                long treeVal = t.sum(l, r);
                long startPartial = (l == 0) ? 0 : partialNums[l - 1];
                print((treeVal + partialNums[r] - startPartial + MOD) % MOD);
            }
        }
    }
}
