#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
const int NX = N * 2;
const int MOD = 1e9 + 9;
vector<int> E[N];
int dfn[N], dfe[N];
int A[N], B[N];
int AS[N], BS[N];
int siz[N], belong[N], heavy[N], depth[N];
namespace ST {
const int TYPE_NONE = 0x0;
const int TYPE_ADD = 0x1;
const int TYPE_SET = 0x2;
struct Tag {
  int vx, vy;
  int type;
  inline void clear() { type = vx = vy = 0; }
  Tag() : vx(0), vy(0), type(0) {}
  Tag(int _vx, int _vy, int _type) : vx(_vx), vy(_vy), type(_type) {}
  inline Tag shift(int sx) const {
    long long _vx = vx, _vy = vy;
    return Tag((_vx * A[sx] + _vy * B[sx]) % MOD,
               (_vx * A[sx + 1] + _vy * B[sx + 1]) % MOD, type);
  }
} t[NX];
struct Data {
  int sum;
} d[NX];
int sz[NX], lc[NX], rc[NX], ct = 0;
inline void tag(int p, const Tag& tg) {
  if (tg.type == TYPE_NONE) return;
  if (tg.type == TYPE_ADD) {
    if (t[p].type == TYPE_NONE) t[p].type = TYPE_ADD;
    t[p].vx = (t[p].vx + tg.vx) % MOD;
    t[p].vy = (t[p].vy + tg.vy) % MOD;
    d[p].sum =
        (d[p].sum + 1LL * tg.vx * AS[sz[p] - 1] + 1LL * tg.vy * BS[sz[p] - 1]) %
        MOD;
  } else {
    t[p] = tg;
    d[p].sum =
        (1LL * tg.vx * AS[sz[p] - 1] + 1LL * tg.vy * BS[sz[p] - 1]) % MOD;
  }
}
inline void down(int p) {
  if (t[p].type != TYPE_NONE) {
    tag(lc[p], t[p]);
    Tag tx = t[p];
    tx = tx.shift(sz[lc[p]]);
    tag(rc[p], tx);
    t[p].clear();
  }
}
inline void up(int p) { d[p].sum = (d[lc[p]].sum + d[rc[p]].sum) % MOD; }
void build(int& p, int l, int r) {
  p = ++ct;
  t[p].clear();
  sz[p] = r - l + 1;
  if (l == r) {
    d[p].sum = dfn[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(lc[p], l, mid);
  build(rc[p], mid + 1, r);
  up(p);
}
int tag(int p, int l, int r, int lx, int rx, const Tag& tg) {
  if (lx <= l && r <= rx) {
    tag(p, tg);
    return r - l + 1;
  }
  int mid = (l + r) >> 1;
  down(p);
  int lct = 0;
  if (lx <= mid) {
    lct = tag(lc[p], l, mid, lx, rx, tg);
  }
  if (mid < rx) {
    lct += tag(rc[p], mid + 1, r, lx, rx, tg.shift(lct));
  }
  up(p);
  return lct;
}
template <typename Collector>
void query(int p, int l, int r, int lx, int rx, Collector& c) {
  if (lx <= l && r <= rx) {
    c.collect(d[p]);
    return;
  }
  int mid = (l + r) >> 1;
  down(p);
  if (lx <= mid) query(lc[p], l, mid, lx, rx, c);
  if (mid < rx) query(rc[p], mid + 1, r, lx, rx, c);
  up(p);
}
struct Collector {
  int sum;
  inline void reset() { sum = 0; }
  inline void collect(const Data& d) { sum = (sum + d.sum) % MOD; }
};
}  // namespace ST
int rootA, rootB, n, m;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", dfn + i);
  A[0] = AS[0] = 1;
  B[0] = BS[0] = 0;
  A[1] = 0;
  B[1] = BS[1] = 1;
  AS[1] = 1;
  for (int i = 2; i <= n; ++i) {
    A[i] = (A[i - 1] + A[i - 2]) % MOD;
    AS[i] = (AS[i - 1] + A[i]) % MOD;
    B[i] = (B[i - 1] + B[i - 2]) % MOD;
    BS[i] = (BS[i - 1] + B[i]) % MOD;
  }
  int root;
  ST::build(root, 1, n);
  while (m--) {
    int op, l, r;
    scanf("%d%d%d", &op, &l, &r);
    if (op == 1) {
      static ST::Tag tg;
      tg.vx = 1;
      tg.vy = 1;
      tg.type = ST::TYPE_ADD;
      ST::tag(root, 1, n, l, r, tg);
    } else {
      static ST::Collector _c;
      _c.reset();
      ST::query(root, 1, n, l, r, _c);
      printf("%d\n", _c.sum);
    }
  }
  return 0;
}
int _main() {
  scanf("%d%d", &n, &m);
  A[0] = AS[0] = 1;
  B[0] = BS[0] = 0;
  A[1] = 0;
  B[1] = BS[1] = 1;
  AS[1] = 1;
  for (int i = 2; i <= n; ++i) {
    A[i] = (A[i - 1] + A[i - 2]) % MOD;
    AS[i] = (AS[i - 1] + A[i]) % MOD;
    B[i] = (B[i - 1] + B[i - 2]) % MOD;
    BS[i] = (BS[i - 1] + B[i]) % MOD;
  }
  for (int i = 1; i < n; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    E[u].push_back(v);
    E[v].push_back(u);
  }
  ST::build(rootA, 1, n);
  ST::build(rootB, 1, n);
  while (m--) {
    int op, a, b, c, d;
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d%d%d%d", &a, &b, &c, &d);
    } else if (op == 2) {
      scanf("%d%d", &a, &b);
      ST::Collector _c;
    } else {
      scanf("%d", &a);
    }
  }
  return 0;
}
