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.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

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

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");

	private void run() throws IOException {
		if (new File("input.txt").exists())
			in = new BufferedReader(new FileReader("input.txt"));
		else
			in = new BufferedReader(new InputStreamReader(System.in));
		if (new File("output.txt").exists())
			out = new PrintWriter("output.txt");
		else
			out = new PrintWriter(System.out);

		solve();

		in.close();
		out.close();
	}

	final int maxn = 3 * 100 * 1000 + 100;
	final long mod = 1000 * 1000 * 1000 + 9;

	int n, m;
	int a[] = new int[maxn];

	long f[] = new long[maxn];
	long sf[] = new long[maxn];

	long getSum(int l, int r) {
		if (l == 0)
			return sf[r];
		return ((sf[r] - sf[l - 1]) % mod + mod) % mod;
	}

	void precalc() {
		f[0] = 1;
		f[1] = 1;
		for (int i = 2; i < maxn; i++)
			f[i] = (f[i - 1] + f[i - 2]) % mod;

		sf[0] = f[0];
		for (int i = 1; i < maxn; i++)
			sf[i] = (f[i] + sf[i - 1]) % mod;
	}

	long getValAB(long a, long b, int n) {
		if (n == 0)
			return a;
		if (n == 1)
			return b;
		return (a * f[n - 2] + b * f[n - 1]) % mod;
	}

	long getSumAB(long a, long b, int n) {
		if (n == 0)
			return a;
		long fn = getValAB(a, b, n);
		long fn1 = getValAB(a, b, n - 1);
		return (mod + 2 * fn + fn1 - b) % mod;
	}

	void solve() throws IOException {
		precalc();
		n = nextInt();
		m = nextInt();
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		RSQ rsq = new RSQ(a, n);

		for (int i = 0; i < m; i++) {
			int type = nextInt();
			int l = nextInt() - 1;
			int r = nextInt() - 1;
			if (type == 1)
				rsq.update(l, r);
			else
				out.println(rsq.getSum(l, r));
//			rsq.printState();
		}
	}

	class RSQ {
		int n;
		long tree[];
		long a[];
		long b[];

		public RSQ(int init[], int size) {
			n = 1;
			while (n < size)
				n <<= 1;
			tree = new long[n << 1];
			a = new long[n << 1];
			b = new long[n << 1];

			fill(a, 0);
			fill(b, 0);
			build(1, 0, n - 1, init, size);
		}

		private void build(int v, int l, int r, int init[], int size) {
			if (l == r) {
				if (l < size)
					tree[v] = init[l];
				else
					tree[v] = 0;
				return;
			}
			int m = (l + r) >> 1;
			build(v * 2, l, m, init, size);
			build(v * 2 + 1, m + 1, r, init, size);
			tree[v] = (tree[v * 2] + tree[v * 2 + 1]) % mod;
		}

		private void push(int v, int l, int r) {
			if ((a[v] | b[v]) == 0)
				return;
			if (l == r) {
				tree[v] = (tree[v] + a[v]) % mod;
			} else {
				int m = (l + r) >> 1;

				a[v * 2] = (a[v * 2] + a[v]) % mod;
				b[v * 2] = (b[v * 2] + b[v]) % mod;

				a[v * 2 + 1] = (a[v * 2 + 1] + getValAB(a[v], b[v], m - l + 1)) % mod;
				b[v * 2 + 1] = (b[v * 2 + 1] + getValAB(a[v], b[v], m - l + 2)) % mod;

				tree[v] = (tree[v] + getSumAB(a[v], b[v], r - l)) % mod;
			}
			a[v] = b[v] = 0l;
		}

		public long getSum(int l, int r) {
			return getSum(1, 0, n - 1, l, r);
		}

		private long getSum(int v, int l, int r, int ll, int rr) {
			if (rr < ll)
				return 0;
			push(v, l, r);
//			System.err.println("(" + l + ", " + r + ") " + ll + " " + rr);
			if (l == ll && r == rr)
				return tree[v];
			int m = (l + r) >> 1;
			return (getSum(v * 2, l, m, ll, min(rr, m)) + getSum(v * 2 + 1, m + 1, r, max(ll, m + 1), rr)) % mod;
		}

		public void update(int l, int r) {
			update(1, 0, n - 1, l, r, 0);
		}

		private void update(int v, int l, int r, int ll, int rr, int index) {
//			System.err.println("(" + l + ", " + r + ") " + ll + " " + rr);
			if (rr < ll)
				return;
			push(v, l, r);
			if (l == ll && r == rr) {
				a[v] = (a[v] + f[index]) % mod;
				b[v] = (b[v] + f[index + 1]) % mod;
//				push(v, l, r);
			} else {
				int m = (l + r) >> 1;
				if (rr <= m)
					update(v * 2, l, m, ll, rr, index);
				else if (ll > m)
					update(v * 2 + 1, m + 1, r, ll, rr, index);
				else {
					update(v * 2, l, m, ll, m, index);
					update(v * 2 + 1, m + 1, r, m + 1, rr, index + m - ll + 1);
				}
				// if (l != r)
				// tree[v] = (tree[v * 2] + tree[v * 2 + 1]) % mod;
				tree[v] = (tree[v] + getSumAB(f[index], f[index + 1], rr - ll)) % mod;
//				System.err.println("(" + l + ", " + r + ") val = " + tree[v]);
			}
		}
		
		public void printState() {
			for (int i = 1; i < n * 2; i++)
				System.err.print(tree[i] + " ");
			System.err.println();
			for (int i = 1; i < n * 2; i++)
				System.err.print("(" + a[i] + ", " + b[i] + ") ");
			System.err.println();
		}

	}

	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}

	String nextToken() throws IOException {
		while (!st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		return st.nextToken();
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String str = in.readLine();
			if (str == null)
				return true;
			st = new StringTokenizer(str);
		}
		return false;
	}

}
