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.
#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1e9 + 9;
const long long int Q1 = 691504013;
const long long int Q2 = 308495997;
const long long int Q3 = 276601605;
long long int power(long long int a, long long int n) {
  if (n == 0) return 1ll;
  if (n == 1) return a % MOD;
  long long int q = power(a, n >> 1);
  q = q * q % MOD;
  if (n & 1) q = q * (a % MOD) % MOD;
  return q;
}
long long int inv(long long int a) { return power(a, MOD - 2); }
class SegmentTree {
 public:
  long long int Q, INV;
  struct Node {
    long long sum;
    long long lazy;
    Node() : sum(0), lazy(0){};
    Node(long long int a, long long int c) : sum(a), lazy(c){};
  };
  SegmentTree(int _size, long long int _Q)
      : tree((_size << 3), {0, 0}), Q(_Q), pref(_size + 12) {
    pref[1] = Q;
    for (int i = 2; i <= _size; i++) {
      pref[i] = pref[i - 1] * Q % MOD;
    }
    INV = inv(Q - 1 + MOD);
  };
  void Update(int l, int r) { update(1, 1, ((int)tree.size()) / 8, l, r, Q); }
  long long int Query(int l, int r) {
    return query(1, 1, ((int)tree.size()) / 8, l, r) * Q3 % MOD;
  }

 public:
  vector<Node> tree;
  vector<long long int> pref;
  long long int geoSum(long long int b1, long long int n) {
    long long int tmp = (pref[n] - 1) * INV % MOD;
    tmp = tmp * b1 % MOD;
    return tmp;
  }
  void push(int pos, int l, int r) {
    if (!tree[pos].lazy) return;
    int mid = (l + r) >> 1;
    int lSize = mid - l + 1;
    int rSize = r - mid;
    tree[pos << 1].sum = (tree[pos << 1].sum + geoSum(tree[pos].lazy, lSize));
    if (tree[pos << 1].sum >= MOD) tree[pos << 1].sum -= MOD;
    tree[pos << 1].lazy = (tree[pos << 1].lazy + tree[pos].lazy);
    if (tree[pos << 1].lazy >= MOD) tree[pos << 1].lazy -= MOD;
    long long int b1 = pref[lSize];
    b1 = b1 * tree[pos].lazy % MOD;
    tree[pos << 1 | 1].sum = (tree[pos << 1 | 1].sum + geoSum(b1, rSize));
    if (tree[pos << 1 | 1].sum >= MOD) tree[pos << 1 | 1].sum -= MOD;
    tree[pos << 1 | 1].lazy = (tree[pos << 1 | 1].lazy + b1);
    if (tree[pos << 1 | 1].lazy >= MOD) tree[pos << 1 | 1].lazy -= MOD;
    tree[pos].lazy = 0;
  }
  void update(int pos, int l, int r, int a, int b, long long int d) {
    if (r < a || l > b) return;
    if (a <= l && r <= b) {
      tree[pos].sum = (tree[pos].sum + geoSum(d, r - l + 1));
      if (tree[pos].sum >= MOD) tree[pos].sum -= MOD;
      tree[pos].lazy = (tree[pos].lazy + d);
      if (tree[pos].lazy >= MOD) tree[pos].lazy -= MOD;
      return;
    }
    push(pos, l, r);
    int mid = (l + r) >> 1;
    update(pos << 1, l, mid, a, b, d);
    long long int rd = pref[max(mid - a + 2, 1)];
    update(pos << 1 | 1, mid + 1, r, a, b, rd);
    tree[pos].sum = (tree[pos << 1].sum + tree[pos << 1 | 1].sum);
    if (tree[pos].sum >= MOD) tree[pos].sum -= MOD;
  }
  long long int query(int pos, int l, int r, int a, int b) {
    if (r < a || l > b) return 0;
    push(pos, l, r);
    if (a <= l && r <= b) return tree[pos].sum;
    int mid = (l + r) >> 1;
    long long int res =
        (query(pos << 1, l, mid, a, b) + query(pos << 1 | 1, mid + 1, r, a, b));
    if (res >= MOD) res -= MOD;
    return res;
  }
  void Print() {
    int i = 0;
    for (Node x : tree) {
      if (i > 0) cout << i << " " << x.sum << " " << x.lazy << "\n";
      i++;
      if (i > 31) return;
    }
  }
};
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  vector<long long int> a(n);
  for (int i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
    if (i != 0) {
      a[i] = (a[i] + a[i - 1]);
      if (a[i] >= MOD) a[i] -= MOD;
    }
  }
  SegmentTree tree1(n, Q1), tree2(n, Q2);
  for (; q; q--) {
    int op, l, r;
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1) {
      tree1.Update(l, r);
      tree2.Update(l, r);
    } else {
      long long int res = (tree1.Query(l, r) - tree2.Query(l, r) +
                           (a[r - 1] - ((l - 2 >= 0) ? a[l - 2] : 0))) %
                          MOD;
      if (res < 0) res += MOD;
      printf("%lld\n", res);
    }
  }
  return 0;
}
