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.*;
import java.util.*;

public class cfABBYYCup3E {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	static final int MOD = 1_000_000_000;

	int[] fib;

	class Node {
		int l, r;
		Node left, right;
		int add;
		int sum0, sum1;

		public Node(int l, int r, int[] a) {
			this.l = l;
			this.r = r;
			if (r - l == 1) {
				sum0 = sum1 = a[l];
			} else {
				int mid = (l + r) >> 1;
				left = new Node(l, mid, a);
				right = new Node(mid, r, a);
				update();
			}
//			System.err.println(l + " " + r + " -> " + sum0 + " " + sum1);
		}

		void pushDown() {
			left.add += add;
			if (left.add >= MOD)
				left.add -= MOD;
			right.add += add;
			if (right.add >= MOD)
				right.add -= MOD;
			add = 0;
		}

		void update() {
			sum0 = left.getValue(l) + right.getValue(l);
			if (sum0 >= MOD)
				sum0 -= MOD;
			sum1 = left.getValue(l - 1) + right.getValue(l - 1);
			if (sum1 >= MOD)
				sum1 -= MOD;
		}

		int getValue(int qL) {

			int shift = l - qL;
			int res = (int) (((long) sum0 * fib[shift] + (long) sum1
					* fib[shift + 1]) % MOD);
//			System.err.println(l + " " + r + " " + qL);
//			System.err.println(sum0 + " " + fib[shift] + " " + sum1 + " " + fib[shift + 1]);
//			System.err.println();
			if (res >= MOD)
				res -= MOD;
			res += (int) ((long) add * fibSum(shift, shift + r - l) % MOD);
			if (res >= MOD)
				res -= MOD;
			return res;
		}

		void set(int pos, int newVal) {
			if (l == pos && pos + 1 == r) {
				add = 0;
				sum0 = sum1 = newVal;
			} else {
				pushDown();
				(pos < left.r ? left : right).set(pos, newVal);
				update();
			}
		}

		int get(int qL, int qR) {
			if (qL <= l && r <= qR) {
				return getValue(qL);
			}
			if (qL >= r || l >= qR)
				return 0;
			pushDown();
			int ret = left.get(qL, qR) + right.get(qL, qR);
			if (ret >= MOD)
				ret -= MOD;
			update();
			return ret;
		}

		void add(int qL, int qR, int delta) {
			if (qL <= l && r <= qR) {
				add += delta;
				if (add >= MOD)
					add -= MOD;
				return;
			}
			if (qL >= r || l >= qR)
				return;
			left.add(qL, qR, delta);
			right.add(qL, qR, delta);
			update();
		}

	}

	int[] fibSum;

	int fibSum(int l, int r) {
		int ret = fibSum[r] - fibSum[l];
		if (ret < 0)
			ret += MOD;
		return ret;
	}

	void solve() throws IOException {
		int n = nextInt();
		int m = nextInt();

		fib = new int[n + 3];
		fib[0] = 1;
		fib[1] = 0;
		for (int i = 2; i < n + 3; i++) {
			fib[i] = fib[i - 1] + fib[i - 2];
			if (fib[i] >= MOD)
				fib[i] -= MOD;
		}

		fibSum = new int[n + 2];
		for (int i = 0; i < n + 1; i++) {
			fibSum[i + 1] = fibSum[i] + fib[i + 2];
			if (fibSum[i + 1] >= MOD)
				fibSum[i + 1] -= MOD;
		}

		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}

		Node root = new Node(0, n, a);

		while (m-- > 0) {
			int type = nextInt();
			switch (type) {
			case 1: {
				int pos = nextInt() - 1;
				int newVal = nextInt();
				root.set(pos, newVal);
				break;
			}
			case 2: {
				int left = nextInt() - 1;
				int right = nextInt() - 1;
				out.println(root.get(left, right + 1));
				break;
			}
			case 3: {
				int left = nextInt() - 1;
				int right = nextInt() - 1;
				int add = nextInt();
				root.add(left, right + 1, add);
				break;
			}
			default:
				throw new AssertionError();
			}
		}

	}

	void inp() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new cfABBYYCup3E().inp();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

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

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

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