#include <bits/stdc++.h>   using namespace std;   long long powm(long long base, long long exp, long long mod = 1000000009) {     long long ans = 1;     while (exp) {       if (exp & 1) ans = (ans * base) % mod;       exp >>= 1, base = (base * base) % mod;     }     return ans;   }   long long ctl(char x, char an =  a ) { return (long long)(x - an); }   char ltc(long long x, char an =  a ) { return (char)(x + an); }   long long first[300005], pref[300005], pref_fib[300005], a[300005];   long long get_fibo_sum(long long l, long long r) {     return (pref_fib[r] - (l ? pref_fib[l - 1] : 0) + 1000000009) % 1000000009;   }   long long get_fibo(long long st1, long long st2, long long i) {     if (i == 0)       return st1;     else if (i == 1)       return st2;     else {       long long ret = ((first[i - 1] * st2) % 1000000009 +                        (first[i - 2] * st1) % 1000000009) %                       1000000009;       return ret;     }   }   long long get_fibo_sum(long long st1, long long st2, long long i) {     if (i == 0)       return st1;     else if (i == 1)       return (st1 + st2) % 1000000009;     else {       long long ans = (st2 * get_fibo_sum(1, i - 1)) % 1000000009;       ans = (ans + (st1 * get_fibo_sum(0, i - 2)) % 1000000009) % 1000000009;       ans = (ans + st1) % 1000000009;       ans = (ans + st2) % 1000000009;       return ans;     }   }   const pair<long long, long long> khali = make_pair(0LL, 0LL);   struct lazySegTree {     long long tree[4 * 300005], x, y, val;     pair<long long, long long> lazy[4 * 300005];     void push(long long low, long long high, long long pos) {       if (lazy[pos] != khali) {         tree[pos] +=             get_fibo_sum(lazy[pos].first, lazy[pos].second, (high - low));         if (low != high) {           pair<long long, long long> tmp;           tmp = lazy[pos];           lazy[2 * pos + 1].first =               (lazy[2 * pos + 1].first + tmp.first) % 1000000009;           lazy[2 * pos + 1].second =               (lazy[2 * pos + 1].second + tmp.second) % 1000000009;           tmp.first = get_fibo(lazy[pos].first, lazy[pos].second,                                (low + high) / 2 - low + 1);           tmp.second = get_fibo(lazy[pos].first, lazy[pos].second,                                 (low + high) / 2 - low + 2);           lazy[2 * pos + 2].first =               (lazy[2 * pos + 2].first + tmp.first) % 1000000009;           lazy[2 * pos + 2].second =               (lazy[2 * pos + 2].second + tmp.second) % 1000000009;         }         lazy[pos] = khali;       }     }     long long query(long long low, long long high, long long pos) {       push(low, high, pos);       if (x <= low and y >= high) return tree[pos];       if (x > high || y < low) return 0;       long long mid = (high + low) / 2;       return (query(low, mid, 2 * pos + 1) + query(mid + 1, high, 2 * pos + 2)) %              1000000009;     }     void update(long long low, long long high, long long pos) {       push(low, high, pos);       if (x > high || y < low) return;       if (x <= low and y >= high) {         lazy[pos].first = first[low - x];         lazy[pos].second = first[low - x + 1];         push(low, high, pos);         return;       }       long long mid = (low + high) / 2;       update(low, mid, 2 * pos + 1), update(mid + 1, high, 2 * pos + 2);       tree[pos] = (tree[2 * pos + 1] + tree[2 * pos + 2]) % 1000000009;     }   } lst;   int main() {     first[0] = 1, first[1] = 1;     for (long long i = 2; i < 300005; i++)       first[i] = (first[i - 1] + first[i - 2]) % 1000000009;     for (long long i = 0; i < 4 * 300005; i++) lst.lazy[i] = khali;     long long type, l, r, n, q;     cin >> n >> q;     for (long long i = 1; i < n + 1; i++) cin >> a[i];     pref_fib[0] = 1;     for (long long i = 1; i < 300005; i++)       pref_fib[i] = (pref_fib[i - 1] + first[i]) % 1000000009;     pref[1] = a[1];     for (long long i = 1; i < 300005; i++)       pref[i] = (pref[i - 1] + a[i]) % 1000000009;     while (q--) {       cin >> type >> l >> r;       lst.x = l, lst.y = r;       if (type == 1) {         lst.update(1, n, 0);       } else {         long long ans = lst.query(1, n, 0);         ans = (ans + pref[r]) % 1000000009;         ans = (ans - pref[l - 1] + 1000000009) % 1000000009;         cout << ans <<   n ;       }     }     return 0;   }   