#include <bits/stdc++.h>   const int N = 1e6 + 5, P = 1e9 + 9;   inline int ksm(int a, int b) {     int r = 1;     for (; b; b >>= 1, a = (long long)a * a % P)       if (b & 1) r = (long long)r * a % P;     return r;   }   int n, q, a[N], t[N], f[N], F[N];   struct mat {     int s[2][2];     inline friend mat operator+(mat a, mat b) {       return a.s[0][0] = (a.s[0][0] + b.s[0][0]) % P,              a.s[0][1] = (a.s[0][1] + b.s[0][1]) % P,              a.s[1][0] = (a.s[1][0] + b.s[1][0]) % P,              a.s[1][1] = (a.s[1][1] + b.s[1][1]) % P, a;     }     inline friend mat operator*(mat a, mat b) {       mat c;       c.s[0][0] =           ((long long)a.s[0][0] * b.s[0][0] + (long long)a.s[0][1] * b.s[1][0]) %           P,       c.s[0][1] =           ((long long)a.s[0][0] * b.s[0][1] + (long long)a.s[0][1] * b.s[1][1]) %           P,       c.s[1][0] =           ((long long)a.s[1][0] * b.s[0][0] + (long long)a.s[1][1] * b.s[1][0]) %           P,       c.s[1][1] =           ((long long)a.s[1][0] * b.s[0][1] + (long long)a.s[1][1] * b.s[1][1]) %           P;       return c;     }     inline friend bool operator!=(mat a, mat b) {       return a.s[0][0] != b.s[0][0] || a.s[0][1] != b.s[0][1] ||              a.s[1][0] != b.s[1][0] || a.s[1][1] != b.s[1][1];     }     inline bool INV(mat &b) {       long long x = (long long)s[0][0] * s[1][1] - (long long)s[0][1] * s[1][0];       if (!x) return 0;       if (x > 0)         x = ksm(x % P, P - 2), b.s[0][0] = (long long)x * s[1][1] % P,         b.s[1][1] = x * s[0][0] % P, b.s[0][1] = x * (P - s[0][1]) % P,         b.s[1][0] = x * (P - s[1][0]) % P;       else         x = ksm((-x) % P, P - 2), b.s[0][0] = (long long)x * (P - s[1][1]) % P,         b.s[1][1] = x * (P - s[0][0]) % P, b.s[0][1] = x * s[0][1] % P,         b.s[1][0] = x * s[1][0] % P;       return 1;     }   } E, Z, O, lz[N];   inline mat ksm(mat a, int b) {     mat r = E;     for (; b; b >>= 1, a = a * a)       if (b & 1) r = r * a;     return r;   }   inline int sum(int l, int r, mat v) {     return ((long long)(F[r] - F[l - 1] + P) * v.s[1][1] +             (long long)(F[r + 1] - F[l] + P) * v.s[1][0]) %            P;   }   inline void tg(int p, int l, int r, mat v) {     lz[p] = lz[p] + v, t[p] = (t[p] + sum(l, r, v)) % P;   }   inline void pushdown(int p, int l, int r, int mid) {     if (lz[p] != O)       tg(p << 1, l, mid, lz[p]), tg(p << 1 | 1, mid + 1, r, lz[p]), lz[p] = O;   }   inline void build(int p, int l, int r) {     if (l == r) {       t[p] = a[l];       return;     }     int mid = l + r >> 1;     build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r),         t[p] = (t[p << 1] + t[p << 1 | 1]) % P;   }   inline void add(int p, int l, int r, int x, int y, mat v) {     if (l >= x && r <= y) return tg(p, l, r, v);     int mid = l + r >> 1;     pushdown(p, l, r, mid);     if (x <= mid) add(p << 1, l, mid, x, y, v);     if (y > mid) add(p << 1 | 1, mid + 1, r, x, y, v);     t[p] = (t[p << 1] + t[p << 1 | 1]) % P;   }   inline int query(int p, int l, int r, int x, int y) {     if (l >= x && r <= y) return t[p];     int mid = l + r >> 1, res = 0;     pushdown(p, l, r, mid);     if (x <= mid) res = (res + query(p << 1, l, mid, x, y)) % P;     if (y > mid) res = (res + query(p << 1 | 1, mid + 1, r, x, y)) % P;     return res;   }   int main() {     scanf( %d%d , &n, &q);     int i, l, r, v;     mat x, y;     for (i = 1; i <= n; i++) scanf( %d , a + i);     build(1, 1, n);     for (f[1] = f[2] = 1, i = 3; i < N; i++) f[i] = (f[i - 1] + f[i - 2]) % P;     for (i = 1; i < N; i++) F[i] = (F[i - 1] + f[i]) % P;     E.s[0][0] = E.s[1][1] = Z.s[0][0] = Z.s[0][1] = Z.s[1][0] = 1;     while (q--)       if (scanf( %d%d%d , &i, &l, &r), i > 1)         printf( %d n , query(1, 1, n, l, r));       else         x = ksm(Z, l - 1), x.INV(y) && (add(1, 1, n, l, r, y), 0);     return 0;   }   