func_code_string: #include <bits/stdc++.h>   using namespace std;   const int MOD = 1e9 + 9;   const int N = 333333;   int fib[N][2], fibSum[N][2];   void PreSolve() {     fib[1][0] = fib[2][1] = 1;     for (int i = 3; i < N; ++i) {       for (int j = 0; j < 2; ++j) {         fib[i][j] = fib[i - 1][j] + fib[i - 2][j];         if (fib[i][j] >= MOD) {           fib[i][j] -= MOD;         }       }     }     for (int i = 1; i < N; ++i) {       for (int j = 0; j < 2; ++j) {         fibSum[i][j] = fibSum[i - 1][j] + fib[i][j];         if (fibSum[i][j] >= MOD) {           fibSum[i][j] -= MOD;         }       }     }   }   void Add(int &a, const int b) {     a += b;     if (a >= MOD) {       a -= MOD;     }   }   int sum[N << 2], add[N << 2][2];   void Up(const int rt) {     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];     if (sum[rt] >= MOD) {       sum[rt] -= MOD;     }   }   void Down(const int len, const int rt) {     if (add[rt][0] || add[rt][1]) {       int ls = rt << 1, rs = rt << 1 | 1;       int rl = len >> 1, ll = len - rl;       int temp[2];       for (int i = 0; i < 2; ++i) {         Add(add[ls][i], add[rt][i]);         Add(add[rs][i], temp[i] = ((long long)add[rt][0] * fib[ll + i + 1][0] +                                    (long long)add[rt][1] * fib[ll + i + 1][1]) %                                   MOD);       }       Add(sum[ls], ((long long)add[rt][0] * fibSum[ll][0] +                     (long long)add[rt][1] * fibSum[ll][1]) %                        MOD);       Add(sum[rs], ((long long)temp[0] * fibSum[rl][0] +                     (long long)temp[1] * fibSum[rl][1]) %                        MOD);       add[rt][0] = add[rt][1] = 0;     }   }   void Build(int l, int r, int rt) {     add[rt][0] = add[rt][1] = 0;     if (l == r) {       cin >> sum[rt];       return;     }     int m = l + r >> 1;     Build(l, m, rt << 1);     Build(m + 1, r, rt << 1 | 1);     Up(rt);   }   void Update(int L, int R, int l, int r, int rt) {     if (L <= l && r <= R) {       int temp[2];       for (int i = 0; i < 2; ++i) {         Add(add[rt][i],             temp[i] = (fib[l - L + i + 1][0] + fib[l - L + i + 1][1]) % MOD);       }       Add(sum[rt], ((long long)fibSum[r - l + 1][0] * temp[0] +                     (long long)fibSum[r - l + 1][1] * temp[1]) %                        MOD);       return;     }     int m = l + r >> 1;     Down(r - l + 1, rt);     if (L <= m) {       Update(L, R, l, m, rt << 1);     }     if (m < R) {       Update(L, R, m + 1, r, rt << 1 | 1);     }     Up(rt);   }   int Query(int L, int R, int l, int r, int rt) {     if (L <= l && r <= R) {       return sum[rt];     }     int m = l + r >> 1, result = 0;     Down(r - l + 1, rt);     if (L <= m) {       Add(result, Query(L, R, l, m, rt << 1));     }     if (m < R) {       Add(result, Query(L, R, m + 1, r, rt << 1 | 1));     }     Up(rt);     return result;   }   int main() {     int n, m;     PreSolve();     while (cin >> n >> m) {       Build(1, n, 1);       int op, x, y;       for (int i = 0; i < m; ++i) {         cin >> op >> x >> y;         if (op == 1) {           Update(x, y, 1, n, 1);         } else {           cout << Query(x, y, 1, n, 1) << endl;         }       }     }     return 0;   }   