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.IOException;
import java.io.InputStreamReader;
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Agostinho Junior (junior94)
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
	OutputWriter out;
	InputReader in;
	public static final XMath math = new XMath((long)1e9 + 9);

	public void solve(int testNumber, InputReader in, OutputWriter out) {
		this.in = in;
		this.out = out;
		int N = in.readInt();
		int M = in.readInt();
		long[] A = new long[N + 1];
		for (int i = 1; i <= N; i++) {
			A[i] = math.mod(in.readInt() + A[i - 1]);
		}
		Node.fa = new long[N + 10];
		Node.fb = new long[N + 10];
		Node.fa[0] = 1;
		for (int i = 1; i < Node.fa.length; i++) {
			Node.fb[i] = math.mod(Node.fa[i - 1] + Node.fb[i - 1]);
			Node.fa[i] = Node.fb[i - 1];
		}
		Node root = new Node(1, N);
		while (M-- > 0) {
			int op = in.readInt();
			int l = in.readInt();
			int r = in.readInt();
			switch (op) {
				case 1:
					root.update(1, 1, l, r);
					break;
				case 2:
					out.println(math.mod(root.get(l, r) + A[r] - A[l - 1]));
					break;
			}
			//out.printfln("%d %d %d", op, l, r);
			//out.printfln("Current State:\n%s", root);
		}
	}
}

class Node {
	private final int s;
	private final int e;
	private Node[] children;
	private long ca;
	private long cb;
	private long sum;
	static long[] fa;
	static long[] fb;
	final static XMath math = TaskC.math;
	public Node(int s, int e) {
		this.s = s;
		this.e = e;
		if (s < e) {
			int mid = (s + e) / 2;
			children = new Node[2];
			children[0] = new Node(s, mid);
			children[1] = new Node(mid + 1, e);
		}
	}
	public long get(int l, int r) {
		if (s > r || l > e) {
			return 0;
		}
		if (l <= s && e <= r) {
			return sum;
		}
		propagate();
		long res = 0;
		for (Node child: children) {
			child.updateSum();
			res = math.mod(res + child.get(l, r));
		}
		return res;
	}
	public void update(long a, long b, int l, int r) {
		if (l > r) {
			l = 0;
			r = 0;
		}
		if (l <= s && e <= r) {
			ca = math.mod(ca + a);
			cb = math.mod(cb + b);
		} else if (s <= r && l <= e) {
			propagate();
			for (Node child: children) {
				int d = Math.max(child.s - l, 0);
				long nextA = math.mod(a * fa[d] + b * fb[d]);
				long nextB = math.mod(a * fa[d + 1] + b * fb[d + 1]);
				child.update(nextA, nextB, l + d, r);
			}
		}
		updateSum();
	}
	private void propagate() {
		if (Math.max(ca, cb) == 0) {
			return;
		}
		for (Node child : children) {
			int d = child.s - s;
			child.ca = math.mod(child.ca + ca * fa[d] + cb * fb[d]);
			child.cb = math.mod(child.cb + ca * fa[d + 1] + cb * fb[d + 1]);
		}
		ca = 0;
		cb = 0;
	}
	private void updateSum() {
		int k = e - s;
		if (s < e) {
			sum = math.mod(children[0].sum + children[1].sum);
		} else {
			sum = 0;
		}
		sum = math.mod(sum + ca * fa[k + 2] + cb * fb[k + 2] - cb);
	}
	public String toString() {
		if (sum == 0) {
			return "";
		}
		String res = String.format("s: %d, e: %d, ca: %d, cb: %d, sum: %d", s, e, ca, cb, sum);
		if (s < e) {
			res += "\n" + children[0] + "\n" + children[1];
		}
		return res;
	}
}

class OutputWriter {
	private PrintWriter output;
	public OutputWriter() {
		this(System.out);
	}
	public OutputWriter(OutputStream out) {
		output = new PrintWriter(out);
	}
	public OutputWriter(Writer writer) {
		output = new PrintWriter(writer);
	}

	public void println(Object o) {
		output.println(o);
	}

	public void close() {
		output.close();
	}
}

class InputReader {
	private BufferedReader input;
	private StringTokenizer line = new StringTokenizer("");
	public InputReader() {
		this(System.in);
	}
	public InputReader(InputStream in) {
		input = new BufferedReader(new InputStreamReader(in));
	}
	public InputReader(String s) {
		try {
			input = new BufferedReader(new FileReader(s));
		} catch(IOException io) { io.printStackTrace(); System.exit(0);}
	}
	public void fill() {
		try {
			if(!line.hasMoreTokens()) line = new StringTokenizer(input.readLine());
		} catch(IOException io) { io.printStackTrace(); System.exit(0);}
	}

	public int readInt() {
		fill();
		return Integer.parseInt(line.nextToken());
	}
}

class XMath {

	private long MOD;

	public XMath(long MOD) {
		this.MOD = MOD;
	}

	public long mod(long x) {
		return mod(x, MOD);
	}

	public static long mod(long n, long MOD) {
		if (n < MOD) {
			if (n < 0) {
				return mod(n + MOD * (Long.MAX_VALUE / MOD), MOD);
			}
			return n;
		}
		return n % MOD;
	}

}

