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>
const int N = 300002;
long long mod = 1000 * 1000 * 1000 + 9;
long long fib[N], sfib[N];
void precalc() {
  fib[0] = sfib[0] = 1;
  fib[1] = 1;
  sfib[1] = 2;
  for (int i = 2; i < N; ++i) {
    fib[i] = (fib[i - 1] + fib[i - 2]);
    if (fib[i] >= mod) {
      fib[i] -= mod;
    }
    sfib[i] = (sfib[i - 1] + fib[i]);
    if (sfib[i] >= mod) {
      sfib[i] -= mod;
    }
  }
}
long long get_fib(int c) {
  if (c < 0) {
    if (c == -2) {
      return 1;
    }
    return 0;
  }
  return fib[c];
}
long long get_fib_sum(int c) {
  if (c < 0) {
    return 0;
  }
  return sfib[c];
}
long long first_fib(long long a, long long b, int c) {
  return (a * get_fib(c - 2) + b * get_fib(c - 1)) % mod;
}
struct IntervalTree {
 public:
  long long f1, f2, lb, rb, su;
  IntervalTree *lt, *rt;
  IntervalTree() {
    f1 = f2 = lb = rb = su = 0;
    lt = rt = nullptr;
  }
  void build(int l, int r) {
    if (l == r) {
      lb = l;
      rb = r;
      return;
    }
    lt = new IntervalTree();
    rt = new IntervalTree();
    lb = l;
    rb = r;
    lt->build(l, (l + r) / 2);
    rt->build((l + r) / 2 + 1, r);
  }
  long long get(int l, int r) {
    push();
    if (r < lb || rb < l) {
      return 0;
    }
    if (l <= lb && rb <= r) {
      return su;
    }
    long long res = (lt->get(l, r) + rt->get(l, r));
    if (res >= mod) {
      res -= mod;
    }
    return res;
  }
  void update(int p, long long v) {
    push();
    if (lb == rb) {
      su = v;
      return;
    }
    if ((lb + rb) / 2 < p) {
      rt->update(p, v);
    } else {
      lt->update(p, v);
    }
    update();
  }
  void update(int l, int r, int uf1, int uf2) {
    push();
    if (r < lb || rb < l) {
      return;
    }
    if (l <= lb && rb <= r) {
      f1 = (f1 + first_fib(uf1, uf2, lb - l));
      if (f1 >= mod) {
        f1 -= mod;
      }
      f2 = (f2 + first_fib(uf1, uf2, lb - l + 1));
      if (f2 >= mod) {
        f2 -= mod;
      }
      push();
      return;
    }
    lt->update(l, r, uf1, uf2);
    rt->update(l, r, uf1, uf2);
    update();
  }
  void update() { su = (lt->su + rt->su) % mod; }
  void push() {
    if (lt != nullptr) {
      lt->f1 = (lt->f1 + f1);
      lt->f2 = (lt->f2 + f2);
      if (lt->f1 >= mod) {
        lt->f1 -= mod;
      }
      if (lt->f2 >= mod) {
        lt->f2 -= mod;
      }
    }
    if (rt != nullptr) {
      int dist = rt->lb - lb;
      rt->f1 = (rt->f1 + first_fib(f1, f2, dist));
      rt->f2 = (rt->f2 + first_fib(f1, f2, dist + 1));
      if (rt->f1 >= mod) {
        rt->f1 -= mod;
      }
      if (rt->f2 >= mod) {
        rt->f2 -= mod;
      }
    }
    int dist = rb - lb;
    su += (get_fib_sum(dist - 1) * f2 + get_fib_sum(dist - 2) * f1 + f1);
    su %= mod;
    f1 = f2 = 0;
  }
};
IntervalTree *tree = new IntervalTree();
void solve() {
  int n, m, t;
  std::cin >> n >> m;
  tree->build(1, n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &t);
    tree->update(i + 1, t);
  }
  int l, r;
  for (int i = 0; i < m; ++i) {
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      tree->update(l, r, 1, 1);
    } else {
      printf("%d\n", tree->get(l, r));
    }
  }
}
int main() {
  precalc();
  solve();
  return 0;
}
