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.BufferedReader;
import java.io.InputStreamReader;


public class E {
	static long M = 1000L*1000*1000;
	static long A(long x, long y) { return (x+y)%M; }
	static long M(long x, long y) { return (x*y)%M; }
	
	static class Node {
		int ll;
		int rr;
		Node l;
		Node r;
		long s0;
		long s1;
		int size;
		long incr;
		public Node(int ll, int rr) {
			this.ll = ll;
			this.rr = rr;
			this.size = rr-ll;
		}
		void do_incr(long by) {
			s0 = A(s0, M(PRE[size], by));
			s1 = A(s1, M(PRE[size+1]-1, by));
			incr = incr+by;
		}
		void push_down() {
			if(incr > 0 && !leaf()) {
				l.do_incr(incr);
				r.do_incr(incr);
				incr = 0;
			}
		}
		void fix() {
			this.s0 = A(l.s0, r.sum(l.size));
			this.s1 = A(l.s1, r.sum(l.size+1));
			
		}
		long sum(int start) {
			return A(
					M(FIB[start][0], s0),
					M(FIB[start][1], s1));
		}
		boolean leaf() { return l==null && r==null; }
	}
	static Node root;
	static Node mk_tree(int ll, int rr) {
		Node n = new Node(ll, rr);
		if(ll+1==rr) {
			n.s0 = A[ll];
			n.s1 = A[ll];
		} else {
			int m = (ll+rr)/2;
			n.l = mk_tree(ll, m);
			n.r = mk_tree(m, rr);
			n.fix();
		}
		return n;
	}
	
	static void set(int i, int x) { _set(i,x,root); }
	static void _set(int i, int x, Node n) {
		if(n.leaf()) {
			n.s0 = x;
			n.s1 = x;
			return;
		}
		n.push_down();
		int m = (n.ll+n.rr)/2;
		if(i < m) _set(i,x,n.l);
		else _set(i,x,n.r);
		n.fix();
	}
	
	static long sum(int l, int r) { return _sum(l,r,root); }
	static long _sum(int ll, int rr, Node n) {
		if(ll<=n.ll && n.rr<=rr) return n.sum(n.ll-ll);
		if(n.rr <= ll || n.ll>=rr) return 0;
		n.push_down();
		return A(_sum(ll,rr,n.l), _sum(ll,rr,n.r));
	}
	static void incr(int ll, int rr, int by) { _incr(ll, rr, by, root); }
	static void _incr(int ll, int rr, int by, Node n) {
		if(ll<=n.ll && n.rr<=rr) {
			n.do_incr(by);
			return;
		}
		if(n.rr <= ll || n.ll>=rr) return;
		n.push_down();
		_incr(ll, rr, by, n.l);
		_incr(ll, rr, by, n.r);
		n.fix();
	}
	
	static long[] PRE;
	static long[][] FIB;
	static int[] A;
	static int i(String s) { return Integer.parseInt(s); }
	public static void main(String[] args) throws Exception {
		FIB = new long[5*100*1000][2];
		PRE = new long[5*100*1000+1];
		FIB[0] = new long[]{1,0};
		FIB[1] = new long[]{0,1};
		for(int i=2; i<FIB.length; i++) {
			FIB[i][0] = A(FIB[i-1][0], FIB[i-2][0]);
			FIB[i][1] = A(FIB[i-1][1], FIB[i-2][1]);
		}
		PRE[0] = 0;
		for(int i=1; i<=FIB.length; i++) {
			PRE[i] = A(PRE[i-1], A(FIB[i-1][0], FIB[i-1][1]));
		}
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] arr = in.readLine().split(" ");
		int n = i(arr[0]);
		int m = i(arr[1]);
		A = new int[n];
		arr = in.readLine().split(" ");
		for(int i=0; i<n; i++)
			A[i] = i(arr[i]);
		root = mk_tree(0, n);
		
		StringBuilder out = new StringBuilder();
		for(int i=0; i<m; i++) {
			arr = in.readLine().split(" ");
			int typ = i(arr[0]);
			if(typ==1) {
				int ix = i(arr[1])-1;
				int v = i(arr[2]);
				set(ix, v);
			} else if(typ==2) {
				int ll = i(arr[1])-1;
				int rr = i(arr[2]);
				out.append(sum(ll,rr));
				out.append('\n');
			} else if(typ==3) {
				int ll = i(arr[1])-1;
				int rr = i(arr[2]);
				int by = i(arr[3]);
				incr(ll, rr, by);
			}
		}
		System.out.print(out);
	}
}
