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

public class Source {
	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		PrintWriter ou = new PrintWriter(System.out);		
		MainCode obj = new MainCode();
		obj.Solve(in, ou);		
		ou.close();
	}
	
}

class MainCode {
	private final int A = 276601605;
	private final int B = 691504013;
	private final int C = 308495997;
	private final int P = 1000000009;
	
	public void Solve(InputReader inp, PrintWriter out) {
		int n = inp.nextInt();
		int q = inp.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; ++i) a[i] = inp.nextInt();
		
		int[] S = new int[n + 1]; S[n] = 0;
		for (int i = n - 1; i >= 0; --i) S[i] = (S[i + 1] + a[i]) % P;
		
		SegmentTree S1 = new SegmentTree(n, B, P);
		SegmentTree S2 = new SegmentTree(n, C, P);
		while (q --> 0) {
			int k = inp.nextInt();
			int l = inp.nextInt() - 1;
			int r = inp.nextInt() - 1;
			if (k == 1) {
				S1.Update(l, r);
				S2.Update(l, r);
			}
			else {
				long sumB = S1.GetSum(l, r);
				long sumC = S2.GetSum(l, r);
				out.println((S[l] + P - S[r + 1] + A * (sumB + P - sumC)) % P);
			}
		}
	}
	
}

class SegmentTree {
	private int M;
	private long[] F, S;
	
	private int n;
	private int[] left, size;
	private long[] tree, lazy;
	
	public SegmentTree(int n, int P, int M) {
		this.n = n;
		this.M = M;
		lazy = new long[n];
		tree = new long[2 * n];
		left = new int[2 * n];
		size = new int[2 * n];
		for (int i = 0; i < n; ++i) {
			tree[i + n] = 0;
			left[i + n] = i;
			size[i + n] = 1;
		}
		for (int i = n - 1; i > 0; --i) {
			tree[i] = Sum(tree[i << 1], tree[i << 1 | 1]);
			left[i] = left[i << 1];
			size[i] = size[i << 1] + size[i << 1 | 1];
		}
		
		F = new long[n + 1]; F[0] = 1; 
		S = new long[n + 1]; S[0] = 1;
		for (int i = 1; i <= n; ++i) F[i] = F[i - 1] * P % M;
		for (int i = 1; i <= n; ++i) S[i] = (S[i - 1] + F[i]) % M;
	}
	
	private long Sum(long a, long b) {
		long res = a + b;
		if (res >= M) res -= M;
		return res;
	}
	
	private void Apply(int k, long v) {
		tree[k] = Sum(tree[k], S[size[k] - 1] * v % M);
		if (k < n) lazy[k] = Sum(lazy[k], v);
	}
	
	private void PushUp(int k) {
		while (k > 1) {
			k >>= 1;
			tree[k] = Sum(tree[k << 1], tree[k << 1 | 1]);
			tree[k] = Sum(tree[k], lazy[k] * S[size[k] - 1] % M);
		}
	}
	
	private void PushDown(int k) {
		for (int i = 20; i > 0; --i) {
			int r = k >> i;
			if (lazy[r] != 0) {
				Apply(r << 1 | 0, lazy[r]);
				Apply(r << 1 | 1, lazy[r] * F[size[r << 1]] % M);
				lazy[r] = 0;
			}
		}
	}
	
	public void Update(int l, int r) {
		int copyL = l; l += n;
		int copyR = r; r += n;
		PushDown(l);
		PushDown(r);
		for (; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
			if ((l & 1) == 1) {
				Apply(l, F[left[l] - copyL + 1]);
				l++;
			}
			if ((r & 1) == 0) {
				Apply(r, F[left[r] - copyL + 1]);
				r--;
			}
		}
		PushUp(copyL + n);
		PushUp(copyR + n);
	}
	
	public int GetSum(int l, int r) {
		long res = 0;
		PushDown(l + n); l += n;
		PushDown(r + n); r += n;
		for (; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
			if ((l & 1) == 1) res = Sum(res, tree[l++]);
			if ((r & 1) == 0) res = Sum(res, tree[r--]);
		}
		return (int)res;
	}
	
}
 
class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

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

}