#include <bits/stdc++.h>
using namespace std;
const int tt = 1e9 + 9;
int N, M;
int F[300005], A[300005];
long long x1[1200005], x2[1200005], val[1200005];
void push_up(int x, int len) {
  val[x] = (val[x << 1] + val[x << 1 | 1] + x1[x] * F[len] +
            x2[x] * (F[len + 1] - 1)) %
           tt;
}
void push_down(int x, int lenl, int lenr) {
  x1[x << 1] = (x1[x << 1] + x1[x]) % tt;
  x2[x << 1] = (x2[x << 1] + x2[x]) % tt;
  x1[x << 1 | 1] =
      (x1[x << 1 | 1] + x1[x] * F[lenl - 1] + x2[x] * F[lenl]) % tt;
  x2[x << 1 | 1] =
      (x2[x << 1 | 1] + x1[x] * F[lenl] + x2[x] * F[lenl + 1]) % tt;
  x1[x] = x2[x] = 0;
  push_up(x << 1, lenl);
  push_up(x << 1 | 1, lenr);
}
void Update(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    x1[x] = (x1[x] + F[l - L + 1]) % tt;
    x2[x] = (x2[x] + F[l - L + 2]) % tt;
    push_up(x, r - l + 1);
    return;
  }
  int mid = (l + r) >> 1;
  push_down(x, mid - l + 1, r - mid);
  if (L <= mid) Update(x << 1, l, mid, L, R);
  if (R > mid) Update(x << 1 | 1, mid + 1, r, L, R);
  push_up(x, r - l + 1);
}
long long Query(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return val[x];
  int mid = (l + r) >> 1;
  long long ans = 0;
  push_down(x, mid - l + 1, r - mid);
  if (L <= mid) ans = (ans + Query(x << 1, l, mid, L, R));
  if (R > mid) ans = (ans + Query(x << 1 | 1, mid + 1, r, L, R));
  return ans;
}
int main() {
  scanf("%d%d", &N, &M);
  F[1] = F[2] = 1;
  for (int i = 1; i <= N; i++) {
    scanf("%d", &A[i]);
    A[i] = (A[i] + A[i - 1]) % tt;
    if (i > 2) F[i] = (F[i - 1] + F[i - 2]) % tt;
  }
  F[N + 1] = (F[N] + F[N - 1]) % tt;
  while (M--) {
    int opt, l, r;
    scanf("%d%d%d", &opt, &l, &r);
    if (opt == 1)
      Update(1, 1, N, l, r);
    else
      printf("%lld\n", (Query(1, 1, N, l, r) + A[r] - A[l - 1] + tt) % tt);
  }
  return 0;
}
