By the age of three Smart Beaver mastered all arithmetic operations and got this summer homework from the amazed teacher:

You are given a sequence of integers a1, a2, ..., an. Your task is to perform on it m consecutive operations of the following type:

  1. For given numbers xi and vi assign value vi to element axi. 
  2. For given numbers li and ri you've got to calculate sum <image>, where f0 = f1 = 1 and at i ≥ 2: fi = fi - 1 + fi - 2. 
  3. For a group of three numbers li ri di you should increase value ax by di for all x (li ≤ x ≤ ri). 



Smart Beaver planned a tour around great Canadian lakes, so he asked you to help him solve the given problem.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 2·105) — the number of integers in the sequence and the number of operations, correspondingly. The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 105). Then follow m lines, each describes an operation. Each line starts with an integer ti (1 ≤ ti ≤ 3) — the operation type: 

  * if ti = 1, then next follow two integers xi vi (1 ≤ xi ≤ n, 0 ≤ vi ≤ 105); 
  * if ti = 2, then next follow two integers li ri (1 ≤ li ≤ ri ≤ n); 
  * if ti = 3, then next follow three integers li ri di (1 ≤ li ≤ ri ≤ n, 0 ≤ di ≤ 105). 



The input limits for scoring 30 points are (subproblem E1): 

  * It is guaranteed that n does not exceed 100, m does not exceed 10000 and there will be no queries of the 3-rd type. 



The input limits for scoring 70 points are (subproblems E1+E2): 

  * It is guaranteed that there will be queries of the 1-st and 2-nd type only. 



The input limits for scoring 100 points are (subproblems E1+E2+E3): 

  * No extra limitations. 

Output

For each query print the calculated sum modulo 1000000000 (109).

Examples

Input

5 5
1 3 1 2 4
2 1 4
2 1 5
2 2 4
1 3 10
2 1 5


Output

12
32
8
50


Input

5 4
1 3 1 2 4
3 1 4 1
2 2 4
1 2 10
2 1 5


Output

12
45
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE1 solver = new TaskE1();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE1 {
    static final int MODULO = (int) 1e9;

    static class Summator {
        int[] multipliers;
        int[] delta;
        int[] unitSum;
        int[] sum;
        int n;

        public Summator(int[] multipliers, int[] startingValues) {
            this.multipliers = multipliers;
            this.n = multipliers.length;
            if (startingValues.length != n) throw new RuntimeException();
            delta = new int[4 * n + 10];
            sum = new int[4 * n + 10];
            unitSum = new int[4 * n + 10];
            initTree(0, 0, n - 1, startingValues);
        }

        private void initTree(int root, int rl, int rr, int[] startingValues) {
            if (rl == rr) {
                delta[root] = startingValues[rl];
                sum[root] = (int) (multipliers[rl] * (long) startingValues[rl] % MODULO);
                unitSum[root] = multipliers[rl] % MODULO;
            } else {
                int rm = (rl + rr) / 2;
                initTree(root * 2 + 1, rl, rm, startingValues);
                initTree(root * 2 + 2, rm + 1, rr, startingValues);
                sum[root] = (sum[root * 2 + 1] + sum[root * 2 + 2]) % MODULO;
                unitSum[root] = (unitSum[root * 2 + 1] + unitSum[root * 2 + 2]) % MODULO;
            }
        }

        public void updateValue(int x, int v) {
            internalUpdate(0, 0, n - 1, x, v);
        }

        private void internalUpdate(int root, int rl, int rr, int x, int v) {
            if (rl == rr) {
                if (rl != x) throw new RuntimeException();
                delta[root] = v;
                sum[root] = (int) (multipliers[rl] * (long) v % MODULO);
            } else {
                killDelta(root);
                int rm = (rl + rr) / 2;
                if (x <= rm)
                    internalUpdate(root * 2 + 1, rl, rm, x, v);
                else
                    internalUpdate(root * 2 + 2, rm + 1, rr, x, v);
                sum[root] = (sum[root * 2 + 1] + sum[root * 2 + 2]) % MODULO;
            }
        }

        public int query(int l, int r) {
            return internalQuery(0, 0, n - 1, l, r);
        }

        private int internalQuery(int root, int rl, int rr, int left, int right) {
            if (left > right) return 0;
            if (rl == left && rr == right)
                return sum[root];
            killDelta(root);
            int rm = (rl + rr) / 2;
            return (internalQuery(root * 2 + 1, rl, rm, left, Math.min(right, rm)) + internalQuery(root * 2 + 2, rm + 1, rr, Math.max(rm + 1, left), right)) % MODULO;
        }

        public void rangeUpdate(int left, int right, int by) {
            internalRangeUpdate(0, 0, n - 1, left, right, by);
        }

        private void internalRangeUpdate(int root, int rl, int rr, int left, int right, int by) {
            if (left > right) return;
            if (rl == left && rr == right) {
                delta[root] = (delta[root] + by) % MODULO;
                sum[root] = (int) ((sum[root] + by * (long) unitSum[root]) % MODULO);
                return;
            }
            killDelta(root);
            int rm = (rl + rr) / 2;
            internalRangeUpdate(root * 2 + 1, rl, rm, left, Math.min(right, rm), by);
            internalRangeUpdate(root * 2 + 2, rm + 1, rr, Math.max(rm + 1, left), right, by);
            sum[root] = (sum[root * 2 + 1] + sum[root * 2 + 2]) % MODULO;
        }

        private void killDelta(int root) {
            if (delta[root] == 0) return;
            delta[root * 2 + 1] = (delta[root * 2 + 1] + delta[root]) % MODULO;
            delta[root * 2 + 2] = (delta[root * 2 + 2] + delta[root]) % MODULO;
            sum[root * 2 + 1] = (int) ((sum[root * 2 + 1] + delta[root] * (long) unitSum[root * 2 + 1]) % MODULO);
            sum[root * 2 + 2] = (int) ((sum[root * 2 + 2] + delta[root] * (long) unitSum[root * 2 + 2]) % MODULO);
            delta[root] = 0;
        }
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int m = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = in.nextInt();
        int[] f = new int[n + 1];
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i < n + 1; ++i) {
            f[i] = (f[i - 1] + f[i - 2]);
            if (f[i] >= MODULO) f[i] -= MODULO;
        }
        Summator s1 = new Summator(subArray(f, 0, n), a);
        Summator s2 = new Summator(subArray(f, 1, n), a);

        for (int i = 0; i < m; ++i) {
            int t = in.nextInt();
            switch (t) {
                case 1: {
                    int x = in.nextInt() - 1;
                    int v = in.nextInt();
                    s1.updateValue(x, v);
                    s2.updateValue(x, v);
                    break;
                }

                case 2: {
                    int l = in.nextInt() - 1;
                    int r = in.nextInt() - 1;
                    int a1 = s1.query(l, r);
                    int a2 = s2.query(l, r);
                    if (l == 0) out.println(a2); else {
                        long res = (a2 * (long) f[l - 1] - a1 * (long) f[l]) % MODULO;
                        if (l % 2 != 0) res = -res;
                        out.println((res + MODULO) % MODULO);
                    }
                    break;
                }

                case 3: {
                    int l = in.nextInt() - 1;
                    int r = in.nextInt() - 1;
                    int d = in.nextInt();
                    s1.rangeUpdate(l, r, d);
                    s2.rangeUpdate(l, r, d);
                    break;
                }
            }
        }
    }

    private int[] subArray(int[] f, int start, int len) {
        int[] res = new int[len];
        System.arraycopy(f, start, res, 0, len);
        return res;
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    }

