func_code_string: #include <bits/stdc++.h>   using namespace std;   inline int in() {     int x;     scanf( %d , &x);     return x;   }   const int N = 2 * 1e5 + 10;   const long long MOD = 1e9;   const long double eps = 1e-12;   int n, m;   long long fib[N], fib_sum[N], g0[4 * N], g1[4 * N], lazy[4 * N];   void precalc() {     fib[0] = fib[1] = 1;     for (int i = 2; i < N; i++) fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;     for (int i = 0; i < N; i++) fib_sum[i + 1] = (fib_sum[i] + fib[i]) % MOD;   }   long long get_gib(int i, int x) {     if (x == 0) return g0[i];     if (x == 1) return g1[i];     long long res = 0;     res = g0[i] * fib[x - 2] + g1[i] * fib[x - 1];     res %= MOD;     return res;   }   void pull(int i, int l, int r) {     int m = (l + r) / 2, cl = i * 2 + 0, cr = i * 2 + 1;     g0[i] = g0[cl] + get_gib(cr, m - l);     g0[i] %= MOD;     g1[i] = g1[cl] + get_gib(cr, m - l + 1);     g1[i] %= MOD;   }   void upd(int id, int len, int add) {     g0[id] += add * fib_sum[len];     g0[id] %= MOD;     g1[id] += add * fib_sum[len + 1] - add;     g1[id] %= MOD;   }   void push(int idx, int l, int r) {     if (lazy[idx] <= 0) return;     int a = lazy[idx], cl = idx * 2 + 0, cr = idx * 2 + 1, m = (l + r) / 2;     upd(cl, m - l, a);     upd(cr, r - m, a);     lazy[cl] += a;     lazy[cr] += a;   }   void turn(int pos, int val, int l = 0, int r = n, int idx = 1) {     if (pos < l || r <= pos) return;     if (r - l < 2) {       g0[idx] = val, g1[idx] = val;       return;     }     push(idx, l, r);     int m = (l + r) / 2;     turn(pos, val, l, m, idx * 2 + 0);     turn(pos, val, m, r, idx * 2 + 1);     pull(idx, l, r);   }   void inc(int ql, int qr, int val, int l = 0, int r = n, int idx = 1) {     if (qr <= l || r <= ql) return;     if (ql <= l && r <= qr) {       upd(idx, r - l, val);       lazy[idx] += val;       return;     }     push(idx, l, r);     int m = (l + r) / 2;     inc(ql, qr, l, m, idx * 2 + 0);     inc(ql, qr, m, r, idx * 2 + 1);     pull(idx, l, r);   }   long long get(int ql, int qr, int l = 0, int r = n, int idx = 1) {     if (qr <= l || r <= ql) return 0;     if (ql <= l && r <= qr) {       return get_gib(idx, l - ql);     }     push(idx, l, r);     long long res = 0;     int m = (l + r) / 2;     res += get(ql, qr, l, m, idx * 2 + 0);     res += get(ql, qr, m, r, idx * 2 + 1);     return res % MOD;   }   int main() {     precalc();     n = in();     m = in();     for (int i = 0; i < n; i++) {       int a = in();       turn(i, a);     }     for (int i = 0; i < m; i++) {       int t = in();       if (t == 1) {         int x = in(), v = in();         x--;         turn(x, v);       } else if (t == 2) {         int l = in(), r = in();         l--;         long long res = (get(l, r) + MOD) % MOD;         printf( %I64d n , res);       } else {         int l = in(), r = in(), d = in();         l--;         inc(l, r, d);       }     }     return 0;   }   