func_code_string: #include <bits/stdc++.h>   using namespace std;   const int maxn = 300110;   const int mod = 1e9 + 9;   int n, m;   int sumv[maxn * 4];   int f1[maxn * 4];   int f2[maxn * 4];   int num[maxn];   int sum[maxn];   int f[maxn];   int addv(int a, int b, int n) {     return ((((long long)f[n + 1] * (long long)b) % mod +              ((long long)f[n] * (long long)a) % mod) %                 mod +             (mod - b) % mod) %            mod;   }   int get(int a, int b, int n) {     return ((long long)f[n - 1] * (long long)b +             ((long long)f[n - 2] * (long long)a) % mod) %            mod;   }   void maintain(int o, int l, int r) {     int lc = o * 2, rc = lc + 1;     sumv[o] = 0;     if (r > l) sumv[o] = (sumv[lc] + sumv[rc]) % mod;     sumv[o] =         ((sumv[o] + ((long long)f[r - l + 2] * (long long)(f2[o])) % mod) % mod +          ((((long long)f[r - l + 1] * (long long)(f1[o])) % mod +            (mod - f2[o]) % mod) %           mod)) %         mod;   }   void update(int o, int l, int r, int yl, int yr) {     int lc = o * 2, rc = lc + 1;     int m = l + (r - l) / 2;     if (yl <= l && yr >= r) {       f1[o] = (f1[o] + f[l - yl + 1]) % mod;       f2[o] = (f2[o] + f[l - yl + 2]) % mod;     } else {       if (yl <= m) update(lc, l, m, yl, yr);       if (yr > m) update(rc, m + 1, r, yl, yr);     }     maintain(o, l, r);   }   int _sum;   void query(int o, int l, int r, int ql, int qr, int add_f1, int add_f2) {     int lc = o * 2, rc = lc + 1;     int m = l + (r - l) / 2;     if (ql <= l && qr >= r) {       _sum = ((_sum + sumv[o]) % mod + addv(add_f1, add_f2, r - l + 1)) % mod;     } else {       if (ql <= m)         query(lc, l, m, ql, qr, (add_f1 + f1[o]) % mod, (add_f2 + f2[o]) % mod);       if (qr > m)         query(rc, m + 1, r, ql, qr,               get((add_f1 + f1[o]) % mod, (add_f2 + f2[o]) % mod, m + 2 - l),               get((add_f1 + f1[o]) % mod, (add_f2 + f2[o]) % mod, m + 3 - l));     }   }   int main() {     memset(sumv, 0, sizeof(sumv));     memset(f1, 0, sizeof(f1));     memset(f2, 0, sizeof(f2));     f[0] = 0;     f[1] = 1;     f[2] = 1;     for (int i = 3; i < maxn; ++i) f[i] = (f[i - 1] + f[i - 2]) % mod;     scanf( %d%d , &n, &m);     for (int i = 1; i <= n; ++i) scanf( %d , &num[i]);     sum[0] = 0;     for (int i = 1; i <= n; ++i) sum[i] = (sum[i - 1] + num[i]) % mod;     int x, y, z;     for (int i = 0; i < m; ++i) {       scanf( %d%d%d , &x, &y, &z);       if (x == 1)         update(1, 1, n, y, z);       else {         _sum = 0;         query(1, 1, n, y, z, 0, 0);         _sum = (_sum + (sum[z] - sum[y - 1] + mod) % mod) % mod;         printf( %d n , _sum);       }     }     return 0;   }   