#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return x * f;
}
const long long N = 600005, mod = 1e9 + 9;
long long f[N], sum[N << 2], A1[N << 2], A2[N << 2], s[N];
void add(long long &x, long long y) {
  x += y;
  if (x >= mod) x -= mod;
}
long long h(long long a1, long long a2, long long n) {
  if (n == 1) return a1;
  if (n == 2) return a2;
  return (1ll * a1 * f[n - 2] + 1ll * a2 * f[n - 1]) % mod;
}
long long getsum(long long a1, long long a2, long long n) {
  if (n == 1) return a1;
  if (n == 2) return (a1 + a2) % mod;
  return (h(a1, a2, n + 2) - a2 + mod) % mod;
}
void Cover(long long rt, long long a1, long long a2, long long n) {
  add(A1[rt], a1);
  add(A2[rt], a2);
  sum[rt] = (sum[rt] + getsum(a1, a2, n)) % mod;
}
void pushdown(long long rt, long long len) {
  long long ls = (len + 1) / 2, a1 = h(A1[rt], A2[rt], ls + 1),
            a2 = h(A1[rt], A2[rt], ls + 2);
  Cover(rt << 1, A1[rt], A2[rt], ls);
  Cover(rt << 1 | 1, a1, a2, len - ls);
  A1[rt] = A2[rt] = 0;
}
void update(long long l, long long r, long long rt, long long L, long long R) {
  if (L <= l && r <= R) {
    Cover(rt, f[l - L + 1], f[l - L + 2], r - l + 1);
    return;
  }
  if (A1[rt]) pushdown(rt, r - l + 1);
  long long mid = (l + r) >> 1;
  if (L <= mid) update(l, mid, rt << 1, L, R);
  if (R > mid) update(mid + 1, r, rt << 1 | 1, L, R);
  sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % mod;
}
long long query(long long l, long long r, long long rt, long long L,
                long long R) {
  if (L <= l && r <= R) return sum[rt];
  if (A1[rt]) pushdown(rt, r - l + 1);
  long long mid = (l + r) >> 1, res = 0;
  if (L <= mid) res = query(l, mid, rt << 1, L, R);
  if (R > mid) res = (res + query(mid + 1, r, rt << 1 | 1, L, R)) % mod;
  return res;
}
signed main() {
  long long n = read(), q = read();
  for (long long i = 1; i <= n; ++i) s[i] = (s[i - 1] + read()) % mod;
  f[1] = 1, f[2] = 1;
  for (long long i = 3; i <= n + 10; ++i) f[i] = (f[i - 1] + f[i - 2]) % mod;
  while (q--) {
    long long opt = read(), l = read(), r = read();
    if (opt == 1)
      update(1, n, 1, l, r);
    else if (opt == 2)
      printf("%d\n",
             (query(1, n, 1, l, r) + (s[r] - s[l - 1] + mod) % mod) % mod);
  }
  return 0;
}
