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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.PriorityQueue;
import java.util.Queue;

public class ProblemC {

    static final long MOD = 1000000009;

    public static class SegmentTree {
        int N;
        long base;
        long[] add;
        long[] sum;
        long[] basePow;
        long[] basePowSum;

        SegmentTree(long b, int n) {
            N = Integer.highestOneBit(n)<<1;
            add = new long[N<<1];
            sum = new long[N<<1];

            base = b;
            basePow = new long[N+1];
            basePow[0] = 1;
            for (int i = 1 ; i < basePow.length ; i++) {
                basePow[i] = (basePow[i-1] * base) % MOD;
            }
            basePowSum = new long[N+2];
            for (int i = 0 ; i < basePow.length ; i++) {
                basePowSum[i+1] = basePowSum[i] + basePow[i];
                basePowSum[i+1] = (basePowSum[i+1] >= MOD) ? basePowSum[i+1] - MOD : basePowSum[i+1];
            }
        }

        void send(int idx, int fr, int to) {
            if (add[idx] >= 1) {
                int med = (fr+to)>>1;
                update(fr, to, add[idx], (idx<<1)+1, fr, med);
                update(fr, to, add[idx], (idx<<1)+2, med, to);
                add[idx] = 0;
            }
        }

        // [l,r)
        long sum(int l, int r) {
            return sum(l, r, 0, 0, N);
        }

        long sum(int l, int r, int idx, int fr, int to) {
            if (to <= l || r <= fr) {
                return 0;
            }
            if (l <= fr && to <= r) {
                return sum[idx];
            } else {
                send(idx, fr, to);

                int med = (fr + to) >> 1;
                long ret = sum(l, r, (idx<<1)+1, fr, med) + sum(l, r, (idx<<1)+2, med, to);
                ret = (ret >= MOD) ? ret - MOD : ret;
                return ret;
            }
        }

        void update(int l, int r, long base) {
            base %= MOD;
            update(l, r, base, 0, 0, N);
        }

        void update(int l, int r, long mul, int idx, int fr, int to) {
            if (to <= l || r <= fr) {
                return;
            }

            if (l <= fr && to <= r) {
                long first = basePow[fr - l];
                first *= mul;
                first %= MOD;
                int len = to - fr;
                add[idx] += first;
                add[idx] = (add[idx] >= MOD) ? add[idx] - MOD : add[idx];
                sum[idx] += (first * basePowSum[len]) % MOD;
                sum[idx] = (sum[idx] >= MOD) ? sum[idx] - MOD : sum[idx];
            } else {
                send(idx, fr, to);

                int med = (fr + to) >> 1;
                int len = med - l;
                update(l, r, mul, idx*2+1, fr, med);
                update(l, r, mul, idx*2+2, med, to);
                sum[idx] = sum[idx*2+1] + sum[idx*2+2];
                sum[idx] = (sum[idx] >= MOD) ? sum[idx] - MOD : sum[idx];
            }
        }
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int m = in.nextInt();

        long[] a = new long[n+1];
        for (int i = 1 ; i <= n ; i++) {
            a[i] = a[i-1] + in.nextInt();
            a[i] %= MOD;
        }


        long Z = 276601605L;
        SegmentTree seg1 = new SegmentTree(691504013L, n+1);
        SegmentTree seg2 = new SegmentTree(308495997L, n+1);
        for (int i = 0 ; i < m ; i++) {
            int type = in.nextInt();
            int l = in.nextInt()-1;
            int r = in.nextInt();
            if (type == 1) {
                seg1.update(l, r, seg1.base);
                seg2.update(l, r, seg2.base);
            } else {
                long sum = (seg1.sum(l, r) - seg2.sum(l, r) + MOD) % MOD;
                sum *= Z;
                sum %= MOD;
                sum += a[r] - a[l] + MOD;
                sum %= MOD;
                out.println(sum);
            }
        }
        out.flush();
    }

    public static void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }


    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int next() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}
