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.util.*;
import java.io.*;

public class DZYLovesFibonacciNumbers {
	// My original approach to the problem was inefficient at calculating multiple
	// fibonacci sums over intervals.

	// All we need to keep track of the first 2 digits of the sequence
	// that will go over the interval because if a sequence starts off with (a1, b1)
	// and (a2, b2) all over the same interval, we can take the general fibonacci sequence
	// where the sequence starts with (a1+a2, b1+b2). This allows me to do a single sum over an
	// interval rather than multiple sums.
	// Once I have the general sequence set up as some (a1+a2+...+an, b1+b2+...+bn), I can
	// use matrix multiplication to calculate the kth term.

	// There is a substitution for matrix multiplication that I will be using.
	// The kth element of a general fibonacci sequence will be defined as f(a, b, k)
	// where a and b are the first 2 elements of this general fibonacci sequence.
	// f(a, b, k) = a*fib[k-2] + b*fib[k-1]

	// These changes should bring my query runtime down to O(log n)
	class SegmentTree { // change
		int n;
		int[] lo, hi;
		long[] sum;
		Delta[] delta;
		public SegmentTree(int n) {
			this.n = n;
			delta = new Delta[4*n+1];
			for(int i = 0 ; i < 4*n+1 ; i++)
				delta[i] = new Delta(0, 0);
			sum = new long[4*n+1];
			lo = new int[4*n+1];
			hi = new int[4*n+1];
			init(1, 0, n-1);
		}
		void construct(long[] arr, int i, int a, int b) {
			if(a == b) {
				sum[i] = arr[a];
				return;
			}
			int m = (a+b)/2;
			construct(arr, 2*i, a, m);
			construct(arr, 2*i+1, m+1, b);
			update(i);
		}
		long sum(int a, int b) {
			return sum(1, a, b);
		}
		void increment(int a, int b, long f, long s) {
			increment(1, a, b, f, s);
		}
		void update(int i) {
			sum[i] = (sum[2*i]+kthTerm(delta[2*i].a, delta[2*i].b, hi[2*i]-lo[2*i]+2)-delta[2*i].b + sum[2*i+1]+kthTerm(delta[2*i+1].a, delta[2*i+1].b, hi[2*i+1]-lo[2*i+1]+2)-delta[2*i+1].b)%MOD;
		}
		void init(int i, int a, int b) {
			lo[i] = a;
			hi[i] = b;
			if(a == b)
				return;
			int m = (a+b)/2;
			init(2*i, a, m);
			init(2*i+1, m+1, b);
		}
		void prop(int i) {
			delta[2*i].increment(delta[i].a, delta[i].b);
			delta[2*i+1].increment(kthTerm(delta[i].a, delta[i].b, lo[2*i+1]-lo[2*i]), kthTerm(delta[i].a, delta[i].b, lo[2*i+1]-lo[2*i]+1));
			delta[i].reset();
		}
		private void increment(int i, int a, int b, long f, long s) {
			if(b < lo[i] || a > hi[i])
				return;
			if(a <= lo[i] && b >= hi[i]) {
				delta[i].increment(kthTerm(f, s, lo[i]-a), kthTerm(f, s, lo[i]-a+1));
				return;
			}
			prop(i);
			increment(2*i, a, b, f, s);
			increment(2*i+1, a, b, f, s);
			update(i);
		}
		private long sum(int i, int a, int b) {
			if(b < lo[i] || a > hi[i])
				return 0;
			if(a <= lo[i] && b >= hi[i])
				return kthTerm(delta[i].a, delta[i].b, hi[i]-lo[i]+2) - delta[i].b + sum[i];
			prop(i);
			long sumLeft = sum(2*i, a, b);
			long sumRight = sum(2*i+1, a, b);
			update(i);
			return (sumLeft + sumRight)%MOD;
		}
	}
	// delta class keeping track of first 2 terms in
	// general fibonacci sequence across an interval.
	class Delta {
		long a, b;
		public Delta(long a, long b) {
			this.a = a;
			this.b = b;
		}
		void increment(long A, long B) {
			a = (a + A)%MOD;
			b = (b + B)%MOD;
		}
		void reset() {
			a = 0;
			b = 0;
		}
		public String toString() {
			return a + " " + b;
		}
	}
	// finds kth term in a general fibonacci sequence starting with a and b.
	long kthTerm(long a, long b, int k) {
		if(k == 0)
			return a;
		if(k == 1)
			return b;
		return ((a*fib[k-2])%MOD + (b*fib[k-1])%MOD)%MOD;
	}
	// generate fibonacci sequence.
	void init() {
		fib[0] = fib[1] = 1;
		for(int i = 2 ; i < fib.length ; i++)
			fib[i] = (fib[i-1] + fib[i-2])%MOD;
	}
	final long[] fib = new long[300300]; // need 300000 Fibonacci numbers, my bad lol
	final int MOD = (int)1e9+9; // Remember it's mod 1e9+9
	public DZYLovesFibonacciNumbers(Scanner scan, BufferedReader br, PrintWriter out) throws Exception {
		init();
		String[] in = br.readLine().split("\\s+");
		int n = Integer.parseInt(in[0]), q = Integer.parseInt(in[1]);
		long arr[] = new long[n];
		in = br.readLine().split("\\s+");
		for(int i = 0 ; i < n ; i++)
			arr[i] = Long.parseLong(in[i]);
		SegmentTree tree = new SegmentTree(n);
		tree.construct(arr, 1, 0, n-1);
		for(int i = 0 ; i < q ; i++) {
			String[] query = br.readLine().split("\\s+");
			int type = Integer.parseInt(query[0]);
			int a = Integer.parseInt(query[1])-1, b = Integer.parseInt(query[2])-1;
			if(type == 1) {
				tree.increment(a, b, 1, 1);
			} else {
				long sum = tree.sum(a, b)%MOD;
				while(sum < 0)
					sum+=MOD;
				out.println(sum);
			}
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		Scanner scan = new Scanner(System.in);
		new DZYLovesFibonacciNumbers(scan, br, out);
		out.close();
	}
	// naive solution for debugging purposes.
	void test(long[] arr, int type, int a, int b) {
		if(type == 1) {
			for(int i = a ; i <= b ; i++)
				arr[i]+=fib[i-a];
		} else {
			long res = 0;
			for(int i = a ; i <= b ; i++)
				res+=arr[i];
			System.out.println(res);
		}
	}
}
/*

10 1
0 0 0 0 0 0 0 0 0 0
1 2 9


50 25
161 254 648 762 509 898 67 189 622 567 604 32 652 964 427 466 580 817 599 752 598 476 908 7 783 167 1000 117 737 559 534 33 670 855 988 366 241 980 500 308 277 110 86 719 779 69 708 550 24 714
2 3 39
1 10 30
1 6 42
2 13 13
2 38 41
2 6 30
2 29 41
1 18 32
2 12 34
1 7 34
1 31 37
2 15 26
2 3 24
2 1 34
1 19 35
1 7 28
2 6 16
2 4 12
1 37 45
1 4 37
1 1 30
1 11 30
1 16 46
1 17 44
1 45 46
2 13 29
1 8 20
1 1 14
1 26 49
1 17 32
2 4 19
1 23 37
2 18 42
2 1 28
1 4 23
2 38 45

20674
676
33387347
238661
39037903
1389231
57060
31482
2226580
6039
4327


10 5
56 12 68 23 41 29 97 69 79 76
1 3 5
1 8 9
2 3 10
1 7 10
2 1 10


10 10
56 12 68 23 41 29 97 69 79 76
1 3 5
1 8 9
1 7 10
1 5 10
1 2 4
1 5 6
1 1 5
1 8 9
1 2 10
1 2 9


10 20
56 12 68 23 41 29 97 69 79 76
1 3 5
1 8 9
2 3 10
1 7 10
2 1 10
1 5 10
2 2 4
1 2 4
1 5 6
2 1 2
2 4 5
1 1 5
1 8 9
2 5 8
2 4 7
2 9 10
2 4 9
1 2 10
1 2 9
2 7 8

488
563
105
69
71
256
210
175
373
217

4 2
1 2 3 4
1 1 4
2 1 4



4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3

 */