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>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")
using namespace std;
using lld = long long int;
using ulld = unsigned long long int;
using lf = double;
using pii = pair<int, int>;
using pli = pair<lld, int>;
int n, m;
lld a[300009];
lld mat[20][3][3];
lld tmp[3][3];
lld fibo[300009];
void inil() {
  int i, j, k, l;
  fibo[0] = 0;
  fibo[1] = 1;
  for (i = 2; i < 300009; i++) {
    fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1000000009;
  }
  mat[0][0][0] = 1;
  mat[0][0][1] = 1;
  mat[0][0][2] = 0;
  mat[0][1][0] = 1;
  mat[0][1][1] = 0;
  mat[0][1][2] = 0;
  mat[0][2][0] = 0;
  mat[0][2][1] = 1;
  mat[0][2][2] = 1;
  for (l = 1; l < 20; l++) {
    for (i = 0; i < 3; i++) {
      for (j = 0; j < 3; j++) {
        tmp[i][j] = 0;
      }
    }
    for (i = 0; i < 3; i++) {
      for (k = 0; k < 3; k++) {
        for (j = 0; j < 3; j++) {
          tmp[i][j] =
              (tmp[i][j] + mat[l - 1][i][k] * mat[l - 1][k][j]) % 1000000009;
        }
      }
    }
    for (i = 0; i < 3; i++) {
      for (j = 0; j < 3; j++) {
        mat[l][i][j] = tmp[i][j];
      }
    }
  }
}
lld ms[2 * 524288];
int ml[2 * 524288];
struct Z {
  lld f1, f2;
  Z() { f1 = f2 = 0; }
  Z(lld p, lld q) {
    f1 = p % 1000000009;
    f2 = q % 1000000009;
  }
  Z operator+(const Z& z) const { return Z(f1 + z.f1, f2 + z.f2); }
  bool is_zero() { return f1 == 0 && f2 == 0; }
  lld getsum(int level) {
    lld res = 0;
    res = (res + mat[level][2][0] * f2) % 1000000009;
    res = (res + mat[level][2][1] * f1) % 1000000009;
    return res;
  }
  Z getnext(int level) {
    Z res;
    res.f1 = (res.f1 + mat[level][1][0] * f2) % 1000000009;
    res.f1 = (res.f1 + mat[level][1][1] * f1) % 1000000009;
    res.f2 = (res.f2 + mat[level][0][0] * f2) % 1000000009;
    res.f2 = (res.f2 + mat[level][0][1] * f1) % 1000000009;
    return res;
  }
};
Z mb[2 * 524288];
void updatems(int dep, int ql, int qr, int ll, int rr) {
  if (ql <= ll && rr <= qr) {
    mb[dep].f1 = (mb[dep].f1 + fibo[ll - ql + 1]) % 1000000009;
    mb[dep].f2 = (mb[dep].f2 + fibo[ll - ql + 2]) % 1000000009;
    return;
  }
  if (qr < ll || rr < ql) return;
  int mm = (ll + rr) / 2;
  mb[dep * 2] = mb[dep * 2] + mb[dep];
  mb[dep * 2 + 1] = mb[dep * 2 + 1] + mb[dep].getnext(ml[dep * 2]);
  mb[dep] = Z();
  updatems(dep * 2, ql, qr, ll, mm);
  updatems(dep * 2 + 1, ql, qr, mm + 1, rr);
  ms[dep] = (ms[dep * 2] + ms[dep * 2 + 1]) % 1000000009;
  ms[dep] = (ms[dep] + mb[dep * 2].getsum(ml[dep * 2])) % 1000000009;
  ms[dep] = (ms[dep] + mb[dep * 2 + 1].getsum(ml[dep * 2 + 1])) % 1000000009;
}
lld getms(int dep, int ql, int qr, int ll, int rr) {
  if (ql <= ll && rr <= qr) {
    return (ms[dep] + mb[dep].getsum(ml[dep])) % 1000000009;
  }
  if (qr < ll || rr < ql) return 0;
  int mm = (ll + rr) / 2;
  mb[dep * 2] = mb[dep * 2] + mb[dep];
  mb[dep * 2 + 1] = mb[dep * 2 + 1] + mb[dep].getnext(ml[dep * 2]);
  mb[dep] = Z();
  lld res = getms(dep * 2, ql, qr, ll, mm);
  res = (res + getms(dep * 2 + 1, ql, qr, mm + 1, rr)) % 1000000009;
  ms[dep] = (ms[dep * 2] + ms[dep * 2 + 1]) % 1000000009;
  ms[dep] = (ms[dep] + mb[dep * 2].getsum(ml[dep * 2])) % 1000000009;
  ms[dep] = (ms[dep] + mb[dep * 2 + 1].getsum(ml[dep * 2 + 1])) % 1000000009;
  return res;
}
int main() {
  inil();
  int t = 1, tv = 0;
  int i, j, k, l;
  while (t--) {
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
      scanf("%lld", &a[i]);
      ms[i + 524288] = a[i];
      ml[i + 524288] = 0;
    }
    for (; i < 524288; i++) {
      ms[i + 524288] = 0;
      ml[i + 524288] = 0;
    }
    for (i = 524288 - 1; i > 0; i--) {
      ms[i] = ms[i * 2] + ms[i * 2 + 1];
      ml[i] = ml[i * 2] + 1;
    }
    while (m--) {
      int type;
      scanf("%d %d %d", &type, &i, &j);
      i--;
      j--;
      if (type == 1) {
        updatems(1, i, j, 0, 524288 - 1);
      } else {
        lld res = getms(1, i, j, 0, 524288 - 1);
        printf("%lld\n", res);
      }
    }
  }
}
