func_code_string: #include <bits/stdc++.h>   using namespace std;   int n, m, a[300005], op, l, r;   long long fib[300005 + 100];   struct wyh {     long long tagl, tagr, sum;   } tree[300005 * 4];   inline long long getint() {     long long x = 0, f = 1;     char ch = getchar();     while (ch <  0  || ch >  9 ) {       if (ch ==  - ) f = -1;       ch = getchar();     }     while (ch >=  0  && ch <=  9 ) x = x * 10 + ch -  0 , ch = getchar();     return x * f;   }   inline void update(int x) {     tree[x].sum = tree[x * 2].sum + tree[x * 2 + 1].sum;     if (tree[x].sum >= 1000000009) tree[x].sum %= 1000000009;   }   inline void build(int x, int l, int r) {     if (l == r) {       tree[x].sum = a[l];       return;     }     int mid = (l + r) >> 1;     build(x * 2, l, mid), build(x * 2 + 1, mid + 1, r);     update(x);   }   inline void modify(int x, int l, int r, int s, int t, int c, int d);   inline void push(int x, int l, int r) {     if (tree[x].tagl || tree[x].tagr) {       int mid = (l + r) >> 1;       modify(x * 2, l, mid, l, r, tree[x].tagl, tree[x].tagr);       modify(x * 2 + 1, mid + 1, r, l, r, tree[x].tagl, tree[x].tagr);       tree[x].tagl = tree[x].tagr = 0;     }   }   inline long long get(int a, int b, int x) {     if (x == 0) return a;     if (x == 1) return b;     return (a * fib[x - 1] % 1000000009 + b * fib[x] % 1000000009) % 1000000009;   }   inline void modify(int x, int l, int r, int s, int t, int c, int d) {     if (s <= l && t >= r) {       int first, second;       first = get(c, d, l - s), second = get(c, d, l - s + 1);       c = first, d = second;       tree[x].tagl += c, tree[x].tagr += d;       tree[x].tagl %= 1000000009, tree[x].tagr %= 1000000009;       tree[x].sum = (tree[x].sum + get(c, d, r - l + 2) - d) % 1000000009;       return;     }     push(x, l, r);     int mid = (l + r) >> 1;     if (s <= mid) modify(x * 2, l, mid, s, t, c, d);     if (t > mid) modify(x * 2 + 1, mid + 1, r, s, t, c, d);     update(x);   }   inline long long query(int x, int l, int r, int s, int t) {     if (s <= l && t >= r) return tree[x].sum;     int mid = (l + r) >> 1;     push(x, l, r);     long long tmp = 0;     if (s <= mid) tmp += query(x * 2, l, mid, s, t);     if (t > mid) tmp += query(x * 2 + 1, mid + 1, r, s, t);     return tmp;   }   void work() {     n = getint(), m = getint();     for (int i = 1; i <= n; ++i) a[i] = getint();     fib[1] = 1;     for (int i = 2; i <= n + 5; ++i)       fib[i] = (fib[i - 1] + fib[i - 2]) % 1000000009;     build(1, 1, n);     for (int i = 1; i <= m; ++i) {       op = getint(), l = getint(), r = getint();       if (op == 1)         modify(1, 1, n, l, r, 1, 1);       else         printf( %I64d n ,                (query(1, 1, n, l, r) % 1000000009 + 1000000009) % 1000000009);     }   }   int main() {     work();     return 0;   }   