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.util.*;
import java.io.*;
import java.math.*;
import java.awt.geom.*;

import static java.lang.Math.*;

public class Solution implements Runnable {
	
	long mod = 1000000000;
	
	class FenwickTree {
		
		int n;
		long[] t;
		
		public FenwickTree(int n) {
			this.n = n;
			this.t = new long[n];
		}
		
		long get(int r) {
			long ans = 0;
			while (r >= 0) {
				ans += t[r];
				r = (r & (r + 1)) - 1;
			}
			ans %= mod;
			if (ans < 0) {
				ans += mod;
			}
			return ans;
		}
		
		void add(int pos, long val) {
			while (pos < n) {
				t[pos] += val;
				t[pos] %= mod;
				if (t[pos] < 0) {
					t[pos] += mod;
				}
				pos = pos | (pos + 1);
			}
		}
		
		long get(int l, int r) {
			long result = get(r) - get(l - 1);
			result %= mod;
			if (result < 0) {
				result += mod;
			}
			return result;
		}
		
	}
	
	public void solve() throws Exception {
		int n = sc.nextInt(), m = sc.nextInt();
		long[] a = new long[n];
		long[][] fib = new long[2][2 * n + 1];
		int zero = n;
		fib[0][zero] = 1;
		fib[1][zero + 1] = 1;
		for (int i = 2; i <= n; i++) {
			fib[0][zero + i] = fib[0][zero + i - 1] + fib[0][zero + i - 2];
			fib[1][zero + i] = fib[1][zero + i - 1] + fib[1][zero + i - 2];
			fib[0][zero + i] = ((fib[0][zero + i] % mod) + mod) % mod;
			fib[1][zero + i] = ((fib[1][zero + i] % mod) + mod) % mod;
		}
		for (int i = -1; i >= -n; i--) {
			fib[0][zero + i] = fib[0][zero + i + 2] - fib[0][zero + i + 1];
			fib[1][zero + i] = fib[1][zero + i + 2] - fib[1][zero + i + 1];
			fib[0][zero + i] = ((fib[0][zero + i] % mod) + mod) % mod;
			fib[1][zero + i] = ((fib[1][zero + i] % mod) + mod) % mod;
		}
		
		FenwickTree t0 = new FenwickTree(n);
		FenwickTree t1 = new FenwickTree(n);
		
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextLong();
			t0.add(i, a[i] * fib[0][zero + i]);
			t1.add(i, a[i] * fib[1][zero + i]);
		}
		
		for (int i = 0; i < m; i++) {
			int t = sc.nextInt();
			if (t == 1) {
				int x = sc.nextInt() - 1;
				long v = sc.nextLong();
				t0.add(x, (v - a[x]) * fib[0][zero + x]);
				t1.add(x, (v - a[x]) * fib[1][zero + x]);
				a[x] = v;
			} else if (t == 2) {
				int l = sc.nextInt() - 1, r = sc.nextInt() - 1;
				long c0 = t0.get(l, r), c1 = t1.get(l, r);
				long fib0 = fib[0][zero - l] + fib[1][zero - l];
				long fib1 = fib[0][zero - l + 1] + fib[1][zero - l + 1];
				long ans = fib0 * c0 + fib1 * c1;
				ans %= mod;
				if (ans < 0) {
					ans += mod;
				}
				out.println(ans);
			} else {
				throw new Exception();
			}
		}
	}

	static Throwable uncaught;

	BufferedReader in;
	FastScanner sc;
	PrintWriter out;

	@Override
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			sc = new FastScanner(in);
			solve();
		} catch (Throwable uncaught) {
			Solution.uncaught = uncaught;
		} finally {
			out.close();
		}
	}

	public static void main(String[] args) throws Throwable {
		Thread thread = new Thread(null, new Solution(), "", (1 << 26));
		thread.start();
		thread.join();
		if (Solution.uncaught != null) {
			throw Solution.uncaught;
		}
	}

}

class FastScanner {

	BufferedReader in;
	StringTokenizer st;

	public FastScanner(BufferedReader in) {
		this.in = in;
	}

	public String nextToken() throws Exception {
		while (st == null || !st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		return st.nextToken();
	}

	public int nextInt() throws Exception {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws Exception {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws Exception {
		return Double.parseDouble(nextToken());
	}

}