#include <bits/stdc++.h>
using namespace std;
long long cal(long long a, long long b) {
  long long sign = 1;
  if (a < 0) {
    a = -a;
    sign = -sign;
  }
  if (b < 0) {
    b = -b;
    sign = -sign;
  }
  unsigned long long n = (unsigned long long)a * b;
  long long r = n % 4000000000LL;
  return sign < 0 ? -r : r;
}
long long a[200001], BIT[200001], lazy[5 * 200001];
void update(long long i, long long n, long long val) {
  while (i <= n) {
    BIT[i] += val;
    i += i & -i;
  }
}
long get(long long i) {
  long long ret = 0;
  while (i) {
    ret += BIT[i];
    i -= i & -i;
  }
  return ret;
}
struct Num {
  long long a, b, c;
  Num() {}
  Num(long long x, long long y, long long z) {
    a = x;
    b = y;
    c = z;
  }
  Num operator+(const Num &n) {
    Num ret = *this;
    Num t = n;
    long long dif = ret.c - t.c;
    if (dif > 0) {
      long long k = 1LL << dif;
      t.a *= k;
      t.b *= k;
    } else if (dif < 0) {
      dif = -dif;
      long long k = 1LL << dif;
      ret.a *= k;
      ret.b *= k;
      ret.c = t.c;
    }
    ret.a += t.a;
    ret.b += t.b;
    if (ret.c && !(ret.a & 1) && !(ret.b & 1)) {
      ret.c--;
      ret.a >>= 1;
      ret.b >>= 1;
    }
    ret.a %= 4000000000LL;
    ret.b %= 4000000000LL;
    return ret;
  }
  Num operator-(const Num &n) { return *this + Num(-n.a, -n.b, n.c); }
  Num operator*(const Num &n) {
    long long x = (cal(a, n.a) + 5 * cal(b, n.b)) % 4000000000LL;
    long long y = (cal(a, n.b) + cal(b, n.a)) % 4000000000LL;
    long long z = c + n.c;
    while (z && !(x & 1) && !(y & 1)) {
      z--;
      x >>= 1;
      y >>= 1;
    }
    return Num(x, y, z);
  }
  Num operator*(long long n) {
    Num ret = Num(a, b, c);
    if (!n) {
      return Num(0, 0, 0);
    }
    if (ret.c && !(n & 1)) {
      ret.c--;
      n >>= 1;
    }
    ret.a = cal(ret.a, n);
    ret.b = cal(ret.b, n);
    return ret;
  }
  long long get() {
    if (c)
      return ((b / (1LL << (c - 1))) % 1000000000 + 1000000000) % 1000000000;
    return (((b << 1) / (1LL << c)) % 1000000000 + 1000000000) % 1000000000;
  }
};
Num x(1, 1, 1);
Num sx[200001], Sx[200001];
struct Segment {
  long long i, l, r;
  Num val;
  Segment() {}
  Segment(int k, int a, int b, Num c) {
    i = k;
    l = a;
    r = b;
    val = c;
  }
  long long len() { return r - l + 1; }
  void update() {
    if (lazy[i] == 0) return;
    val = val + (Sx[r - l + 1] * lazy[i]);
    if (l < r) {
      lazy[i << 1] += lazy[i];
      lazy[(i << 1) + 1] += lazy[i];
    }
    lazy[i] = 0;
  }
};
Segment T[5 * 200001];
void go(long long i, long long l, long long r) {
  if (l == r) {
    T[i] = Segment(i, l, r, x * a[l]);
    return;
  }
  long long m = (l + r) >> 1;
  go(i << 1, l, m);
  go((i << 1) + 1, m + 1, r);
  Num x = T[i << 1].val + (sx[m - l + 1] * T[(i << 1) + 1].val);
  T[i] = Segment(i, l, r, x);
}
Num get(long long i, long long l, long long r) {
  T[i].update();
  if (l == T[i].l && r == T[i].r) {
    return T[i].val;
  }
  long long m = (T[i].l + T[i].r) >> 1;
  if (r <= m) return get(i << 1, l, r);
  if (l > m) return get((i << 1) + 1, l, r);
  Num left = get(i << 1, l, m);
  Num right = get((i << 1) + 1, m + 1, r);
  return left + (sx[m - l + 1] * right);
}
void update(long long i, long long l, long long r, long long val) {
  if (l == T[i].l && r == T[i].r) {
    lazy[i] += val;
    return;
  }
  long long m = (T[i].l + T[i].r) >> 1;
  if (r <= m) {
    update(i << 1, l, r, val);
  } else if (l > m) {
    update((i << 1) + 1, l, r, val);
  } else {
    update(i << 1, l, m, val);
    update((i << 1) + 1, m + 1, r, val);
  }
  T[i << 1].update();
  T[(i << 1) + 1].update();
  T[i].val = T[i << 1].val + (sx[T[i << 1].len()] * T[(i << 1) + 1].val);
}
int main() {
  long long n, q, i, k, t, v, l, r, d, add;
  scanf("%lld %lld", &n, &q);
  sx[1] = Sx[1] = x;
  for (i = 2; i <= n; i++) {
    sx[i] = sx[i - 1] * x;
    Sx[i] = Sx[i - 1] + sx[i];
  }
  for (i = 1; i <= n; i++) {
    scanf("%lld", a + i);
    update(i, n, a[i]);
    update(i + 1, n, -a[i]);
  }
  go(1, 1, n);
  while (q--) {
    scanf("%lld", &t);
    if (t == 1) {
      scanf("%lld %lld", &k, &v);
      add = v - get(k);
      update(k, n, add);
      update(k + 1, n, -add);
      update(1, k, k, add);
    } else {
      scanf("%lld %lld", &l, &r);
      if (t == 2) {
        printf("%lld\n", get(1, l, r).get());
      } else {
        scanf("%lld", &d);
        update(l, n, d);
        update(r + 1, n, -d);
        update(1, l, r, d);
      }
    }
  }
  return 0;
}
