447_E. DZY Loves Fibonacci Numbers_36737
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.
/**
 * DA-IICT
 * Author : Savaliya Sagar
 */
import java.io.*;
import java.math.*;
import java.util.*;

public class E447 {
	InputStream is;
	PrintWriter out;
	long tree[];
	Pair lazy[];
	long a[];
	int n,m,N=(int) (3e5+5);
	int mod = (int) (1e9+9);
	long pw[][][] = new long[N][2][2];
	void solve() {
		n = ni();
		m = ni();
		a = new long[n+1];
		pw[1][1][0]=pw[1][0][1]=pw[1][0][0]=1;
		for(int i=2;i<N;i++){
			pw[i] = matrixmultyplication(pw[i-1],pw[1]);
		}
		for (int i = 1; i <= n; i++)
			a[i] = add(a[i - 1],ni());
		tree = new long[4 * n];
		lazy = new Pair[4 * n];
		for(int i=0;i<4*n;i++)
			lazy[i] = new Pair(0,0);
		
		while(m-->0){
			int t = ni();
			int l = ni();
			int r = ni();
			if(t==1){
				updateRange(1,1,n,l,r);
			}else{
				long res = sub(a[r],a[l-1]);
				res = add(res,queryRange(1,1,n,l,r));
				out.println(res);
			}
		}
	}
	

	void updateRange(int node, int start, int end, int l, int r) {
		if (lazy[node].u!=0 || lazy[node].v!=0) {
			long F1 = lazy[node].u;
			long F2 = lazy[node].v;
			tree[node] = add(tree[node],sub(fib(end-start+3,F1,F2),F2));
			if(start!=end){
				int mid = (start + end) / 2;
				lazy[2*node].u = add(lazy[2*node].u,F1);
				lazy[2*node].v = add(lazy[2*node].v,F2);
				long f1 = fib(mid-start+2,F1,F2);
				long f2 = fib(mid-start+3,F1,F2);
				lazy[2*node+1].u = add(lazy[2*node+1].u,f1);
				lazy[2*node+1].v = add(lazy[2*node+1].v,f2);
			}
			lazy[node].u = 0;
			lazy[node].v = 0;
		}
		if (start > end || start > r || end < l) 
			return;
		if (start >= l && end <= r) {
			long F1,F2;
			F1 = fib(start-l+1,1,1);
			F2 = fib(start-l+2,1,1);
			tree[node] = add(tree[node],sub(fib(end-start+3,F1,F2),F2));
			if(start!=end){
				int mid = (start + end) / 2;
				lazy[2*node].u = add(lazy[2*node].u,F1);
				lazy[2*node].v = add(lazy[2*node].v,F2);
				long f1 = fib(mid-start+2,F1,F2);
				long f2 = fib(mid-start+3,F1,F2);
				lazy[2*node+1].u = add(lazy[2*node+1].u,f1);
				lazy[2*node+1].v = add(lazy[2*node+1].v,f2);
			}
			return;
		}
		int mid = (start + end) / 2;
		updateRange(node * 2, start, mid, l, r); 
		updateRange(node * 2 + 1, mid + 1, end, l, r);
		tree[node] = add(tree[node * 2],tree[node * 2 + 1]); 
	}

	long queryRange(int node, int start, int end, int l, int r) {
		if (start > end || start > r || end < l)
			return 0;
		if (lazy[node].u!=0 || lazy[node].v!=0) {
			long F1 = lazy[node].u;
			long F2 = lazy[node].v;
			tree[node] = add(tree[node],sub(fib(end-start+3,F1,F2),F2));
			if(start!=end){
				int mid = (start + end) / 2;
				lazy[2*node].u = add(lazy[2*node].u,F1);
				lazy[2*node].v = add(lazy[2*node].v,F2);
				long f1 = fib(mid-start+2,F1,F2);
				long f2 = fib(mid-start+3,F1,F2);
				lazy[2*node+1].u = add(lazy[2*node+1].u,f1);
				lazy[2*node+1].v = add(lazy[2*node+1].v,f2);
			}
			lazy[node].u = 0;
			lazy[node].v = 0;
		}
		if (start >= l && end <= r) 
			return tree[node];
		int mid = (start + end) / 2;
		long p1 = queryRange(node * 2, start, mid, l, r); 
		long p2 = queryRange(node * 2 + 1, mid + 1, end, l, r); 
		return add(p1, p2);
	}
	
	    long fib(int n,long a,long b){
	        if(n==1)
	            return a;
	        if(n==2)
	        	return b;
	        
	        long[][] c = pw[n-2];
	        long ret = add(mul(c[0][0],b),mul(c[0][1],a));
	        return ret;
	    }
	  long[][] matrixmultyplication(long[][] a,long[][] b){
	        long[][] c = new long[2][2];
	        for(int i=0;i<2;i++){
	            for(int j=0;j<2;j++){
	                c[i][j] = 0;
	                for(int k=0;k<2;k++){
	                    c[i][j]=(c[i][j] + ((a[i][k]%mod)*(b[k][j]%mod))%mod)%mod;
	                }
	            }
	        }
	        return c;
	    }
	long add(long a,long b){
		long sum = a+b;
		if(sum>=mod)
			sum -= mod;
		return sum;
	}
	long sub(long a,long b){
		long sub = a-b;
		if(sub<0)
			sub += mod;
		return sub;
	}
	long mul(long a,long b){
		return (a*b)%mod;
	}
	class Pair implements Comparable<Pair> {
		long u;
		long v;

		public Pair(long u, long v) {
			this.u = u;
			this.v = v;
		}

		public int hashCode() {
			int hu = (int) (u ^ (u >>> 32));
			int hv = (int) (v ^ (v >>> 32));
			return 31 * hu + hv;
		}

		public boolean equals(Object o) {
			Pair other = (Pair) o;
			return u == other.u && v == other.v;
		}

		public int compareTo(Pair other) {
			return Long.compare(u, other.u) != 0 ? Long.compare(u, other.u)
					: Long.compare(v, other.v);
		}

		public String toString() {
			return "[u=" + u + ", v=" + v + "]";
		}
	}


	void run() throws Exception {
		String INPUT = "/media/sagar407/D/java workspace/11Input_output/input.txt";
		is = oj ? System.in : new FileInputStream(INPUT);
		out = new PrintWriter(System.out);

		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis() - s + "ms");
	}

	public static void main(String[] args) throws Exception {
		new Thread(null, new Runnable() {
			public void run() {
				try {
					new E447().run();
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;

	private int readByte() {
		if (lenbuf == -1)
			throw new InputMismatchException();
		if (ptrbuf >= lenbuf) {
			ptrbuf = 0;
			try {
				lenbuf = is.read(inbuf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (lenbuf <= 0)
				return -1;
		}
		return inbuf[ptrbuf++];
	}

	private boolean isSpaceChar(int c) {
		return !(c >= 33 && c <= 126);
	}

	private int skip() {
		int b;
		while ((b = readByte()) != -1 && isSpaceChar(b))
			;
		return b;
	}

	private double nd() {
		return Double.parseDouble(ns());
	}

	private char nc() {
		return (char) skip();
	}

	private String ns() {
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	private char[] ns(int n) {
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while (p < n && !(isSpaceChar(b))) {
			buf[p++] = (char) b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}

	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for (int i = 0; i < n; i++)
			map[i] = ns(m);
		return map;
	}

	private int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private int ni() {
		int num = 0, b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private long nl() {
		long num = 0;
		int b;
		boolean minus = false;
		while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
			;
		if (b == '-') {
			minus = true;
			b = readByte();
		}

		while (true) {
			if (b >= '0' && b <= '9') {
				num = num * 10 + (b - '0');
			} else {
				return minus ? -num : num;
			}
			b = readByte();
		}
	}

	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

	private void tr(Object... o) {
		if (!oj)
			System.out.println(Arrays.deepToString(o));
	}
}
4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3
 2 2
1 2
2 1 2
2 1 2
 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
 2 2
1 2
2 1 1
2 1 2
 4 4
1 2 3 8
1 1 4
2 1 4
1 2 4
2 1 3
 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 5 7
2 9 10
2 4 9
1 2 10
1 2 9
2 7 8
 4 4
1 4 3 4
1 1 4
2 1 4
1 2 4
2 1 3
 2 2
2 2
2 1 1
2 1 2
 4 4
1 2 1 8
1 1 4
2 1 4
1 2 4
2 1 3
 10 20
56 12 68 6 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 5 7
2 9 10
2 4 9
1 2 10
1 2 9
2 7 8
 4 4
1 2 1 8
1 1 4
2 2 4
1 2 4
2 1 3
 4 4
1 2 1 4
1 1 4
2 2 4
1 2 4
2 1 3
 2 2
1 2
1 1 2
2 1 2
 4 4
1 2 3 4
2 1 4
2 1 4
1 2 4
2 1 3
 10 20
56 12 68 23 41 29 97 69 79 76
1 3 5
1 8 9
2 3 10
1 3 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 5 7
2 9 10
2 4 9
1 2 10
1 2 9
2 7 8
 4 4
1 2 1 8
1 2 4
2 1 4
1 2 4
2 1 3
 4 4
1 2 1 2
1 1 4
2 2 4
1 2 4
2 1 3
 2 2
0 2
1 1 2
2 1 2
 4 4
1 2 3 4
2 1 4
1 1 4
1 2 4
2 1 3
 4 4
1 4 1 8
1 2 4
2 1 4
1 2 4
2 1 3
 4 4
1 2 1 2
1 1 4
2 2 4
1 2 4
2 1 1
 4 4
1 2 3 4
2 1 4
1 1 4
1 2 4
2 1 4
 4 4
1 2 2 2
1 1 4
2 2 4
1 2 4
2 1 1
 4 4
1 2 3 4
2 1 4
1 1 4
1 2 4
2 2 4
 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 5 9
2 5 8
2 4 7
2 9 10
2 4 9
1 2 10
1 2 9
2 7 8
 2 2
1 2
2 1 1
2 2 2
 4 4
0 2 3 8
1 1 4
2 1 4
1 2 4
2 1 3
 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 3 5
1 1 5
1 8 9
2 5 8
2 5 7
2 9 10
2 4 9
1 2 10
1 2 9
2 7 8
 2 2
2 3
2 1 1
2 1 2
 4 4
1 2 1 8
1 1 4
2 1 4
1 2 4
2 1 2
 10 20
56 12 68 6 41 29 118 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 5 7
2 9 10
2 4 9
1 2 10
1 2 9
2 7 8
 4 4
1 2 1 8
1 1 4
2 2 2
1 2 4
2 1 3
 2 2
1 2
1 1 2
2 2 2
 10 20
10 12 68 23 41 29 97 69 79 76
1 3 5
1 8 9
2 3 10
1 3 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 5 7
2 9 10
2 4 9
1 2 10
1 2 9
2 7 8
 4 3
1 2 1 8
1 2 4
2 1 4
1 2 4
2 1 3
 4 4
0 2 1 2
1 1 4
2 2 4
1 2 4
2 1 3
 4 4
1 2 1 4
1 1 2
2 2 4
1 2 3
2 1 3
 4 4
1 2 1 2
1 1 4
2 2 4
2 2 4
2 1 1
 4 4
0 2 3 8
1 1 4
2 1 3
1 2 4
2 1 3
 4 4
1 2 1 8
1 1 4
2 1 4
1 2 4
2 1 4
 10 20
56 12 68 6 41 29 118 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 5 7
2 9 10
2 4 9
1 2 7
1 2 9
2 7 8
 2 2
1 0
1 1 2
2 2 2
 10 20
10 12 68 23 41 29 97 69 79 76
1 3 5
1 8 9
2 3 10
1 3 3
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 5 7
2 9 10
2 4 9
1 2 10
1 2 9
2 7 8
 4 4
1 2 1 8
2 1 4
2 1 4
1 2 4
2 1 4
 10 20
56 12 68 6 41 29 118 118 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 5 7
2 9 10
2 4 9
1 2 7
1 2 9
2 7 8
 4 4
1 2 1 4
1 1 4
2 2 4
1 2 3
2 1 3
 4 4
1 2 1 10
1 1 4
2 2 2
1 2 4
2 1 3
 4 3
1 2 1 8
1 2 4
2 1 4
1 2 3
2 1 3

17
12
 3
3
 488
563
105
69
71
256
210
175
373
217
 1
3
 21
12
 488
563
105
69
71
256
181
175
373
217
 19
14
 2
4
 19
10
 471
546
88
69
54
256
181
175
356
217
 17
10
 13
10
 5
 10
10
8
 488
610
107
69
74
272
190
204
401
228
 16
8
 11
10
 4
 10
12
 18
10
 11
2
 10
21
 12
2
 10
19
 488
563
105
69
71
262
214
179
383
221
 1
2
 20
11
 488
563
105
69
141
256
181
175
373
217
 2
5
 19
6
 492
567
88
69
54
277
202
175
377
238
 3
10
 3
 488
564
107
23
74
272
190
204
401
228
 16
 11
9
 8
8
 11
11
2
 9
11
 19
23
 492
567
88
69
54
277
202
175
377
225
 1
 488
511
106
23
71
254
180
170
369
215
 12
12
16
 541
616
88
69
54
326
202
175
426
274
 13
10
 3
10
 16
