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 Main {
	FastScanner in;
	PrintWriter out;
	
	final int mod = (int) (1e9 + 9);
	
	int[] fib0, fib1, pfib0, pfib1;
	
	class SegmentTree {
		int[] t;
		int[] f0, f1;
		int[] size;
		int n;
		
		SegmentTree(int[] a) {
			int n = a.length;
			t = new int[4 * n];
			f0 = new int[4 * n];
			f1 = new int[4 * n];
			size = new int[4 * n];
			build(a, 0, 0, n);
		}
		
		void build (int[] a, int v, int tl, int tr) {
			if (tl == tr - 1) {
				t[v] = a[tl];
				size[v] = 1;
			}
			else {
				int tm = (tl + tr) / 2;
				build (a, 2 * v + 1, tl, tm);
				build (a, 2 * v + 2, tm, tr);
				t[v] = (t[2 * v + 1] + t[2 * v + 2]) % mod;
				size[v] = size[2 * v + 1] + size[2 * v + 2];
			}
		}
		
		void push (int v) {
			if (f0[v] + f1[v] != 0) {
				f0[2 * v + 1] = (f0[2 * v + 1] + f0[v]) % mod;
				f1[2 * v + 1] = (f1[2 * v + 1] + f1[v]) % mod;
				int sz = size[2 * v + 1];
				f0[2 * v + 2] = (int)((f0[2 * v + 2] + 1L * fib0[sz] * f0[v] + 1L * fib1[sz] * f1[v]) % mod);
				f1[2 * v + 2] = (int)((f1[2 * v + 2] + 1L * fib0[sz + 1] * f0[v] + 1L * fib1[sz + 1] * f1[v]) % mod);
				f0[v] = f1[v] = 0;
			}
		}
		 
		void update (int v, int tl, int tr, int l, int r, int F0, int F1) {
			if (tl >= r || tr <= l)
				return;
			if (tl >= l && tr <= r) {
				f0[v] = (int) ((f0[v] + 1L * F0 * fib0[tl - l] + 1L * F1 * fib1[tl - l]) % mod);
				f1[v] = (int) ((f1[v] + 1L * F0 * fib0[tl - l + 1] + 1L * F1 * fib1[tl - l + 1]) % mod);
			} else {
				push (v);
				int tm = (tl + tr) / 2;
				update (2 * v + 1, tl, tm, l, r, F0, F1);
				update (2 * v + 2, tm, tr, l, r, F0, F1);
				t[v] = (calc(2 * v + 1) + calc(2 * v + 2)) % mod;
			}
		}
		 
		int calc(int v) {
			int res = (int) ((t[v] + 1L * f0[v] * pfib0[size[v] - 1] + 1L * f1[v] * pfib1[size[v] - 1]) % mod); 
			return res;
		}
		
		int get (int v, int tl, int tr, int l, int r) {
			if (tl >= l && tr <= r)
				return calc(v);
			if (tl >= r || tr <= l)
				return 0;
			push (v);
			int tm = (tl + tr) / 2;
			int res = (get(2 * v + 1, tl, tm, l, r) + get(2 * v + 2, tm, tr, l, r)) % mod;
			t[v] = (calc(2 * v + 1) + calc(2 * v + 2)) % mod;
			return res;
		}
 	}
	
	public void solve() throws IOException {
		int n = in.nextInt(), m = in.nextInt();
		fib0 = new int[n + 2];
		fib1 = new int[n + 2];
		pfib0 = new int[n + 2];
		pfib1 = new int[n + 2];
		fib0[0] = 1; fib1[0] = 0;
		fib0[1] = 0; fib1[1] = 1;
		for (int i = 2; i < n + 2; ++i) {
			fib0[i] = (fib0[i - 1] + fib0[i - 2]) % mod;
			fib1[i] = (fib1[i - 1] + fib1[i - 2]) % mod;
		}
		for (int i = 0; i < n + 2; i++) {
			pfib0[i] = fib0[i];
			pfib1[i] = fib1[i];
			if (i != 0) {
				pfib0[i] = (pfib0[i] + pfib0[i - 1]) % mod;
				pfib1[i] = (pfib1[i] + pfib1[i - 1]) % mod;
			}
		}
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = in.nextInt();
		SegmentTree st = new SegmentTree(a);
		for (int i = 0; i < m; ++i) {
			int type = in.nextInt();
			int l = in.nextInt() - 1, r = in.nextInt();
			if (type == 1) {
				st.update(0, 0, n, l, r, 1, 1);
			} else if (type == 2) {
				int res = st.get(0, 0, n, l, r);
				out.println(res);
			}
		}
	}

	public void run() {
		try {
			in = new FastScanner();
			out = new PrintWriter(System.out);

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}
	}

	public static void main(String[] arg) {
		new Main().run();
	}
}