#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
struct node {
  int a;
  int b;
  int sum;
};
int n, q;
int nblock;
node nums[300315];
int acum = 0;
int fib[300315];
long long auxi;
void add(int &a, int b) {
  a += b;
  if (a > 1000000009) a -= 1000000009;
}
inline int calcf(int x) {
  if (x <= 1 || fib[x] != 0) return fib[x];
  fib[x] = 0;
  add(fib[x], calcf(x - 2));
  add(fib[x], calcf(x - 1));
  return fib[x];
}
inline int sumfibo(int a, int b, int posx, int posy) {
  int x = 0;
  auxi = (1LL * calcf(posx - 1) * a) % (1LL * 1000000009);
  add(x, int(auxi));
  auxi = (1LL * calcf(posx) * b) % (1LL * 1000000009);
  add(x, int(auxi));
  int y = 0;
  auxi = (1LL * calcf(posy) * a) % (1LL * 1000000009);
  add(y, int(auxi));
  auxi = (1LL * calcf(posy + 1) * b) % (1LL * 1000000009);
  add(y, int(auxi));
  add(y, 1000000009 - x);
  return y;
}
inline void update(int ini, int fin) {
  int inc = 1;
  int acumblock = 0;
  if ((ini - 1) / nblock == (fin - 1) / nblock) {
    for (int i = 0; i < nblock; i++) {
      int j = i + ini;
      if (j <= fin) {
        add(acumblock, calcf(inc));
        inc++;
      }
      if (((j - 1) / nblock) == (fin - 1) / nblock) {
        add(nums[j].sum, acumblock);
      }
    }
  } else {
    int iniblock;
    iniblock = ini - ((ini - 1) % nblock);
    int l = iniblock;
    if (ini % nblock != 1) {
      for (int i = ini; i < iniblock + nblock; i++) {
        add(acumblock, calcf(inc));
        inc++;
        add(nums[i].sum, acumblock);
      }
      l = iniblock + nblock;
    }
    while (l + nblock <= fin + 1) {
      add(nums[l].a, calcf(inc));
      add(nums[l].b, calcf(inc + 1));
      inc += nblock;
      l += nblock;
    }
    acumblock = 0;
    for (int i = 0; i < nblock; i++) {
      int j = i + l;
      if (j <= fin) {
        add(acumblock, calcf(inc));
        inc++;
      }
      if (((j - 1) / nblock) == (fin - 1) / nblock) add(nums[j].sum, acumblock);
    }
  }
}
inline int get(int ini, int fin) {
  int iniblock;
  int ans = 0;
  if ((ini - 1) / nblock == (fin - 1) / nblock) {
    iniblock = ini - ((ini - 1) % nblock);
    if (ini % nblock) {
      if (fin % nblock)
        add(ans, sumfibo(nums[iniblock].a, nums[iniblock].b, ini % nblock,
                         fin % nblock));
      else
        add(ans,
            sumfibo(nums[iniblock].a, nums[iniblock].b, ini % nblock, nblock));
    } else
      add(ans, sumfibo(nums[iniblock].a, nums[iniblock].b, nblock, nblock));
    add(ans, nums[fin].sum);
    if (ini % nblock != 1) {
      add(ans, 1000000009 - nums[ini - 1].sum);
    }
    return ans;
  } else {
    iniblock = ini - ((ini - 1) % nblock);
    if (ini % nblock)
      add(ans,
          sumfibo(nums[iniblock].a, nums[iniblock].b, ini % nblock, nblock));
    else
      add(ans, sumfibo(nums[iniblock].a, nums[iniblock].b, nblock, nblock));
    add(ans, nums[iniblock + nblock - 1].sum);
    if (ini % nblock != 1) {
      add(ans, 1000000009 - nums[ini - 1].sum);
    }
    int l = iniblock + nblock;
    while (l + nblock <= fin + 1) {
      add(ans, sumfibo(nums[l].a, nums[l].b, 1, nblock));
      add(ans, nums[l + nblock - 1].sum);
      l += nblock;
    }
    if (l <= fin) {
      add(ans, nums[fin].sum);
      add(ans, sumfibo(nums[l].a, nums[l].b, 1, fin % nblock));
    }
    return ans;
  }
}
int main() {
  fib[0] = 0;
  fib[1] = 1;
  fib[2] = 1;
  scanf("%d %d", &n, &q);
  nblock = int(sqrt(n * 1.0));
  if (nblock * nblock != n) nblock++;
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    add(acum, x);
    nums[i].sum = acum;
    if (i % nblock == 0) acum = 0;
  }
  for (int i = 0; i < q; i++) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    if (x == 1) {
      update(y, z);
    } else if (x == 2) {
      printf("%d\n", get(y, z));
    }
  }
  return 0;
}
