HRY is a pupil. He has just learned about Fibonacci sequence recently, and he made some new sequences : 

fib(i) means the ith element in the Fibonacci sequence :

 

At first this problem is to calculate fid(n), but that is too easy. So after discussing with 10256, they changed the problem:

Given a positive integer array , perform the following two types of operations:

1. Given l,r,x, for all , execute . 

2. Given l,r, calculate. 

输入描述:

The first line of the input contains an integer n, indicating the length of the array.
The second line contains n positive integers separated by spaces, indicating .
The third line contains an integer Q, indicating the number of operations.
For the next Q lines, it is either , indicating the first type of operation, or , indicating the second type of operation.
All values in input are integers.

输出描述:

For each operation of second type, output.

3
1 2 3
6
2 1 3
1 1 3 1
2 1 3
1 1 1 2
1 2 2 3
2 1 3

11
24
74