Zigzag

### 题目描述 一天，WSY同学构造了一个特殊的数列 $S$ ，这个数列除了角标以外还有一个固定的参数 $z$，$S$ 有一个固定的生成规则如下： $i\ge 0$ - 当 $i\mod 2\times(z-1)\le z$ 时，$S_i^z=i\mod 2\times(z-1)$ - 当 $i\mod 2\times(z-1)>z$ 时，$S_i^z=2z-(i\mod 2*(z-1))$ - 特别的，当 $i\mod 2\times(z-1)=0$ 时，$S_i^z=2$ 还有一个长度为 $n$ 的普通数列 $a$ 已经给出，现在让你进行如下操作： 每个操作的第一个数 $op$ 表示操作类型，$op=1$ 即为操作一， $op=2$ 为操作二 - 操作一还包含两个参数 $pos,val$ 表示将 $a_{pos}$ 的值修改为 $val$ - 操作二有三个参数 $l,r,z$ 要求你输出下面算式的结果： $$\sum_{i=l}^r \ \ a_i\times S_i^z$$ ### 输入格式 第一行一个整数 $n$，表示数列 $a$ 的长度 第二行有 $n$ 个整数，表示数列 $a$ 第三行只有一个整数 $m$，表示操作数 接下来 $m$ 行每行描述一个操作，见题目描述。 ### 输出格式 对于每个操作二，输出算式的结果 ### 数据范围 $1\le n,m\le 10^5$ 保证任何时候 $a_i\le 10^9,2\le z\le 6$

The court wizard Zigzag wants to become a famous mathematician. For that, he needs his own theorem, like the Cauchy theorem, or his sum, like the Minkowski sum. But most of all he wants to have his sequence, like the Fibonacci sequence, and his function, like the Euler's totient function. The Zigag's sequence with the zigzag factor z is an infinite sequence $ S_{i}^{z} $ $ (i>=1; z>=2) $ , that is determined as follows: - $ S_{i}^{z}=2 $ , when ; - , when ; - , when . Operation  means taking the remainder from dividing number $ x $ by number $ y $ . For example, the beginning of sequence $ S_{i}^{3} $ (zigzag factor 3) looks as follows: 1, 2, 3, 2, 1, 2, 3, 2, 1. Let's assume that we are given an array $ a $ , consisting of $ n $ integers. Let's define element number $ i $ $ (1<=i<=n) $ of the array as $ a_{i} $ . The Zigzag function is function , where $ l,r,z $ satisfy the inequalities $ 1<=l<=r<=n $ , $ z>=2 $ . To become better acquainted with the Zigzag sequence and the Zigzag function, the wizard offers you to implement the following operations on the given array $ a $ . 1. The assignment operation. The operation parameters are $ (p,v) $ . The operation denotes assigning value $ v $ to the $ p $ -th array element. After the operation is applied, the value of the array element $ a_{p} $ equals $ v $ . 2. The Zigzag operation. The operation parameters are $ (l,r,z) $ . The operation denotes calculating the Zigzag function $ Z(l,r,z) $ . Explore the magical powers of zigzags, implement the described operations.

The first line contains integer $ n $ $ (1<=n<=10^{5}) $ — The number of elements in array $ a $ . The second line contains $ n $ space-separated integers: $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=10^{9}) $ — the elements of the array. The third line contains integer $ m $ $ (1<=m<=10^{5}) $ — the number of operations. Next $ m $ lines contain the operations' descriptions. An operation's description starts with integer $ t_{i} $ $ (1<=t_{i}<=2) $ — the operation type. - If $ t_{i}=1 $ (assignment operation), then on the line follow two space-separated integers: $ p_{i},v_{i} $ $ (1<=p_{i}<=n; 1<=v_{i}<=10^{9}) $ — the parameters of the assigning operation. - If $ t_{i}=2 $ (Zigzag operation), then on the line follow three space-separated integers: $ l_{i},r_{i},z_{i} $ $ (1<=l_{i}<=r_{i}<=n; 2<=z_{i}<=6) $ — the parameters of the Zigzag operation. You should execute the operations in the order, in which they are given in the input.

For each Zigzag operation print the calculated value of the Zigzag function on a single line. Print the values for Zigzag functions in the order, in which they are given in the input. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

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

5
26
38

Explanation of the sample test: - Result of the first operation is $ Z(2,3,2)=3·1+1·2=5 $ . - Result of the second operation is $ Z(1,5,3)=2·1+3·2+1·3+5·2+5·1=26 $ . - After the third operation array $ a $ is equal to $ 2,3,5,5,5 $ . - Result of the forth operation is $ Z(1,5,3)=2·1+3·2+5·3+5·2+5·1=38 $ .