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 int MOD = 1000000009, MAXN = 400500;
struct Tree {
  int sum, a0, a1, l, r;
  Tree(){};
  Tree(int l, int r) : l(l), r(r), sum(0), a0(0), a1(0){};
};
Tree tr[5 * MAXN];
int n, m, a[MAXN], from, f0[MAXN], g0[MAXN], g1[MAXN], f1[MAXN], fib[MAXN];
inline void addMOD(int &x, long long y) { x = (x + y) % MOD; }
void push(int x) {
  if ((tr[x].a0 != 0) || (tr[x].a1 != 0)) {
    int len = tr[x].r - tr[x].l;
    addMOD(tr[x].sum, g0[len] * 1LL * tr[x].a0),
        addMOD(tr[x].sum, g1[len] * 1LL * tr[x].a1);
    if (tr[x].l != tr[x].r)
      addMOD(tr[x + x].a0, tr[x].a0), addMOD(tr[x + x].a1, tr[x].a1),
          addMOD(tr[x + x + 1].a0,
                 tr[x].a0 * 1LL * f0[tr[x + x + 1].l - tr[x].l]),
          addMOD(tr[x + x + 1].a0,
                 tr[x].a1 * 1LL * f1[tr[x + x + 1].l - tr[x].l]),
          addMOD(tr[x + x + 1].a1,
                 tr[x].a0 * 1LL * f0[tr[x + x + 1].l - tr[x].l + 1]),
          addMOD(tr[x + x + 1].a1,
                 tr[x].a1 * 1LL * f1[tr[x + x + 1].l - tr[x].l + 1]);
    tr[x].a0 = 0, tr[x].a1 = 0;
  }
}
inline void upd(int x) {
  tr[x].sum = (tr[x + x].sum + tr[x + x + 1].sum) % MOD,
  addMOD(tr[x].sum, g0[tr[x + x].r - tr[x + x].l] * 1LL * tr[x + x].a0),
  addMOD(tr[x].sum, g1[tr[x + x].r - tr[x + x].l] * 1LL * tr[x + x].a1),
  addMOD(tr[x].sum,
         g0[tr[x + x + 1].r - tr[x + x + 1].l] * 1LL * tr[x + x + 1].a0),
  addMOD(tr[x].sum,
         g1[tr[x + x + 1].r - tr[x + x + 1].l] * 1LL * tr[x + x + 1].a1);
}
void build(int x, int l, int r) {
  tr[x] = Tree(l, r);
  if (l < r) {
    int mid = (l + r) / 2;
    build(x + x, l, mid), build(x + x + 1, mid + 1, r), upd(x);
  } else
    tr[x].sum = a[l];
}
void add(int x, int l, int r) {
  push(x);
  if ((r < tr[x].l) || (l > tr[x].r)) return;
  if ((l <= tr[x].l) && (r >= tr[x].r)) {
    tr[x].a0 += fib[tr[x].l - from], tr[x].a1 += fib[tr[x].l - from + 1];
    return;
  }
  add(x + x, l, r), add(x + x + 1, l, r), upd(x);
}
int fsum(int x, int l, int r) {
  push(x);
  if ((r < tr[x].l) || (l > tr[x].r)) return 0;
  if ((l <= tr[x].l) && (r >= tr[x].r)) return tr[x].sum;
  int res = fsum(x + x, l, r) + fsum(x + x + 1, l, r);
  upd(x);
  if (res >= MOD) res -= MOD;
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  f0[0] = 1, f0[1] = 0, f1[0] = 0, f1[1] = 1, g0[0] = 1, g0[1] = 1, g1[0] = 0,
  g1[1] = 1, fib[0] = 1, fib[1] = 1;
  for (int i = 2; i <= n; i++) {
    fib[i] = (fib[i - 1] + fib[i - 2]) % MOD,
    f0[i] = (f0[i - 1] + f0[i - 2]) % MOD,
    f1[i] = (f1[i - 1] + f1[i - 2]) % MOD, g0[i] = (2 * g0[i - 1]) % MOD;
    if (i > 2) g0[i] = (g0[i] - g0[i - 3] + MOD) % MOD;
    g1[i] = (2 * g1[i - 1]) % MOD;
    if (i > 2) g1[i] = (g1[i] - g1[i - 3] + MOD) % MOD;
  }
  build(1, 0, n - 1);
  for (int i = 0; i < m; i++) {
    int qt, l, r;
    scanf("%d%d%d", &qt, &l, &r), --l, --r, from = l;
    if (qt == 1)
      add(1, l, r);
    else
      printf("%d\n", fsum(1, l, r));
  }
}
