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 CF446C {
	// 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 {
		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 CF446C(JoltyScanner scan, PrintWriter out) throws Exception {
		init();
		int n = scan.nextInt(), q = scan.nextInt();
		long arr[] = new long[n];
		for(int i = 0 ; i < n ; i++)
			arr[i] = scan.nextInt();
		SegmentTree tree = new SegmentTree(n);
		tree.construct(arr, 1, 0, n-1);
		for(int i = 0 ; i < q ; i++) {
			int type = scan.nextInt();
			int a = scan.nextInt() - 1, b = scan.nextInt() - 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 {
		JoltyScanner scan = new JoltyScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		new CF446C(scan, 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);
		}
	}
	static class JoltyScanner {
		public static final int BUFFER_SIZE = 1 << 16;
		public static final char NULL_CHAR = (char) -1;
		byte[] buffer = new byte[BUFFER_SIZE];
		int bufferIdx = 0, size = 0;
		char c = NULL_CHAR;
		BufferedInputStream in;
		public JoltyScanner(InputStream in) {
			this.in = new BufferedInputStream(in, BUFFER_SIZE);
			c = nextChar();
		}
		public int nextInt() {
			while(c < '0' || c > '9')
				c = nextChar();
			int res = 0;
			while(c >= '0' && c <= '9') {
				res = (res << 3) + (res << 1) + c - '0';
				c = nextChar();
			}
			return res;
		}
		public char nextChar() {
			while (bufferIdx == size) {
				try {
					size = in.read(buffer);
				} catch (Exception e) {
					return NULL_CHAR;
				}
				bufferIdx = 0;
			}
			return (char) buffer[bufferIdx++];
		}
	}
}