func_code_string: #include <bits/stdc++.h>   using namespace std;   const long long mod = 1e9 + 9;   struct node {     long long x, y, sum;   } st[1200005];   int n, q, type, L, R, a[300005];   long long f[300005];   void build(int id, int l, int r) {     if (l == r) {       st[id].sum = a[l];       return;     }     int mid = l + r >> 1;     build(id << 1, l, mid);     build(id << 1 | 1, mid + 1, r);     st[id].sum = (st[id << 1].sum + st[id << 1 | 1].sum) % mod;   }   void push(int id, int l, int r) {     if (st[id].x == 0 && st[id].y == 0) return;     int mid = l + r >> 1, pos = mid - l + 2;     long long x = st[id].x, y = st[id].y;     st[id << 1].x = (st[id << 1].x + x) % mod;     st[id << 1].y = (st[id << 1].y + y) % mod;     st[id << 1].sum =         (st[id << 1].sum + x * f[mid - l + 1] + y * (f[mid - l + 2] - 1)) % mod;     st[id << 1 | 1].x =         (st[id << 1 | 1].x + x * f[pos - 2] + y * f[pos - 1]) % mod;     st[id << 1 | 1].y = (st[id << 1 | 1].y + x * f[pos - 1] + y * f[pos]) % mod;     st[id << 1 | 1].sum =         (st[id << 1 | 1].sum + x * f[r - l + 1] + y * (f[r - l + 2] - 1) -          x * f[mid - l + 1] - y * (f[mid - l + 2] - 1) + mod) %         mod;     st[id].x = st[id].y = 0;   }   void update(int id, int l, int r, int u, int v) {     if (l > v or r < u) return;     if (u <= l && r <= v) {       st[id].x = (st[id].x + f[l - u + 1]) % mod;       st[id].y = (st[id].y + f[l - u + 2]) % mod;       st[id].sum = (st[id].sum + f[l - u + 1] * f[r - l + 1] % mod +                     f[l - u + 2] * (f[r - l + 2] - 1)) %                    mod;       return;     }     push(id, l, r);     int mid = l + r >> 1;     update(id << 1, l, mid, u, v);     update(id << 1 | 1, mid + 1, r, u, v);     st[id].sum = (st[id << 1].sum + st[id << 1 | 1].sum) % mod;   }   long long query(int id, int l, int r, int u, int v) {     if (l > v or r < u) return 0;     if (u <= l && r <= v) return st[id].sum;     push(id, l, r);     int mid = l + r >> 1;     return (query(id << 1, l, mid, u, v) + query(id << 1 | 1, mid + 1, r, u, v)) %            mod;   }   signed main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     cin >> n >> q;     f[1] = 1;     for (int i = 1; i <= n; ++i) {       cin >> a[i];       if (i > 1) f[i] = (f[i - 1] + f[i - 2]) % mod;     }     f[n + 1] = (f[n] + f[n - 1]) % mod;     build(1, 1, n);     while (q--) {       cin >> type >> L >> R;       if (type == 1)         update(1, 1, n, L, R);       else         cout << (query(1, 1, n, L, R) + mod) % mod << endl;     }   }   