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
{
	public static final long MOD = 1000000009;
	
	public static long[][][] pow;
	
	public static void main(String[] args) throws Exception
	{
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		int n = in.nextInt();
		int m = in.nextInt();
		
		pow = new long[300001][3][3];
		for(int x = 0; x < 3; x++)
		{
			pow[0][x][x] = 1;
		}
		
		pow[1] = new long[][] { {0, 1, 0}, {1, 1, 0}, {1, 0, 1} };
		for(int y = 2; y < pow.length; y++)
		{
			pow[y] = mult(pow[y - 1], pow[1]);
		}
		
		long[] init = new long[n + 1];
		for(int z = 0; z < n; z++)
		{
			init[z + 1] = init[z] + in.nextInt();
			init[z + 1] %= MOD;
		}
		
		IntervalTree it = new IntervalTree(n);
		for(int a = 0; a < m; a++)
		{
			int type = in.nextInt();
			
			if(type == 1)
			{
				it.inc(in.nextInt() - 1, in.nextInt() - 1);
			}
			else
			{
				int l = in.nextInt();
				int r = in.nextInt();
				
				out.println(((init[r] - init[l - 1] + it.query(l - 1, r - 1)) % MOD + MOD) % MOD);
			}
		}
		
		out.close();
	}
	
	public static long[][] mult(long[][] a, long[][] b)
	{
		long[][] ret = new long[a.length][b[0].length];
		
		for(int r = 0; r < ret.length; r++)
		{
			for(int c = 0; c < ret[r].length; c++)
			{
				for(int i = 0; i < a[0].length; i++)
				{
					ret[r][c] += (a[r][i] * b[i][c]) % MOD;
					ret[r][c] %= MOD;
				}
			}
		}
		
		return ret;
	}
	
	public static long mult2(long m1, long m2, long m3, long a, long b, long c)
	{
		return (m1 * a + m2 * b + m3 * c) % MOD;
	}
	
	static class IntervalTree
	{
		int n;
		long[] tree;
		long[] first;
		long[] second;
		
		public IntervalTree(int n)
		{
			this.n = n;
			tree = new long[4 * n];
			first = new long[4 * n];
			second = new long[4 * n];
		}
		
		public void inc(int left, int right)
		{
			inc(left, right, 1, 0, n - 1);
		}
		
		public void inc(int left, int right, int i, int l, int r)
		{
			if(r < left || l > right)
			{
				return;
			}
			else if(l >= left && r <= right)
			{
				first[i] += mult2(pow[l - left][0][0], pow[l - left][0][1], pow[l - left][0][2], 1, 1, 0);
				first[i] %= MOD;
				second[i] += mult2(pow[l - left][1][0], pow[l - left][1][1], pow[l - left][1][2], 1, 1, 0);
				second[i] %= MOD;
				return;
			}
			else
			{
				prop(i, r - l + 1);
				
				int m = (l + r) / 2;
				inc(left, right, 2 * i, l, m);
				inc(left, right, 2 * i + 1, m + 1, r);
				
				update(i, r - l + 1);
			}
		}
		
		public long query(int left, int right)
		{
			return query(left, right, 1, 0, n - 1);
		}
		
		public long query(int left, int right, int i, int l, int r)
		{
			if(r < left || l > right)
			{
				return 0;
			}
			else if(l >= left && r <= right)
			{
				return (tree[i] + mult2(pow[r - l + 1][2][0], pow[r - l + 1][2][1], pow[r - l + 1][2][2], first[i], second[i], 0)) % MOD;
			}
			else
			{
				prop(i, r - l + 1);
				
				int m = (l + r) / 2;
				long ret = (query(left, right, 2 * i, l, m) + query(left, right, 2 * i + 1, m + 1, r)) % MOD;
				
				update(i, r - l + 1);
				
				return ret;
			}
		}
		
		public void prop(int i, int size)
		{
			first[2 * i] += first[i];
			first[2 * i] %= MOD;
			second[2 * i] += second[i];
			second[2 * i] %= MOD;
			
			first[2 * i + 1] += mult2(pow[(size + 1) / 2][0][0], pow[(size + 1) / 2][0][1], pow[(size + 1) / 2][0][2], first[i], second[i], 0);
			first[2 * i + 1] %= MOD;
			second[2 * i + 1] += mult2(pow[(size + 1) / 2][1][0], pow[(size + 1) / 2][1][1], pow[(size + 1) / 2][1][2], first[i], second[i], 0);
			second[2 * i + 1] %= MOD;
			
			first[i] = 0;
			second[i] = 0;
		}
		
		public void update(int i, int size)
		{
			long leftSum = (tree[2 * i] + mult2(pow[(size + 1) / 2][2][0], pow[(size + 1) / 2][2][1], pow[(size + 1) / 2][2][2], first[2 * i], second[2 * i], 0)) % MOD;
			long rightSum = (tree[2 * i + 1] + mult2(pow[size / 2][2][0], pow[size / 2][2][1], pow[size / 2][2][2], first[2 * i + 1], second[2 * i + 1], 0)) % MOD;
			
			tree[i] = (leftSum + rightSum) % MOD;
		}
	}
	
	static class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream input)
		{
			br = new BufferedReader(new InputStreamReader(input));
			st = new StringTokenizer("");
		}
		
		public String next() throws IOException
		{
			if(st.hasMoreTokens())
			{
				return st.nextToken();
			}
			else
			{
				st = new StringTokenizer(br.readLine());
				return next();
			}
		}
		
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}
	}
}
