CF228D.Zigzag

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.

宫廷巫师之字形（Zigzag）希望成为一名著名的数学家。为此，他需要属于自己的定理，例如柯西定理（Cauchy theorem）；需要属于自己的求和，例如闵可夫斯基和（Minkowski sum）；而最渴望的，则是属于自己的数列（例如斐波那契数列）以及属于自己的函数（例如欧拉函数 $\varphi(n)$）。

之字形因子为 $z$ 的之字形数列 $S_i^z$（其中 $i \geq 1$，$z \geq 2$）是一个无限数列，其定义如下：

• 当 $i \bmod (2z - 2) = 1$ 时，$S_i^z = 1$；
• 当 $1 < i \bmod (2z - 2) \leq z$ 时，$S_i^z = i \bmod (2z - 2)$；
• 当 $z < i \bmod (2z - 2) < 2z - 2$ 时，$S_i^z = 2z - i \bmod (2z - 2)$。

符号 $x \bmod y$ 表示 $x$ 除以 $y$ 所得的余数。例如，数列 $S_i^3$（之字形因子为 $3$）的开头几项为：$1,\ 2,\ 3,\ 2,\ 1,\ 2,\ 3,\ 2,\ 1$。

现给定一个由 $n$ 个整数组成的数组 $a$，记该数组中第 $i$ 个元素（$1 \leq i \leq n$）为 $a_i$。之字形函数定义为

$$Z(l,\ r,\ z) = \sum_{i=l}^{r} a_i \cdot S_{i-l+1}^z,$$

其中参数 $l,\ r,\ z$ 满足不等式 $1 \leq l \leq r \leq n$ 且 $z \geq 2$。

为更深入地理解之字形数列与之字形函数，这位巫师邀请你针对给定数组 $a$ 实现以下两种操作：

1. 赋值操作：操作参数为 $(p,\ v)$，表示将数组第 $p$ 个元素赋值为 $v$。执行该操作后，$a_p = v$。
2. 之字形操作：操作参数为 $(l,\ r,\ z)$，表示计算之字形函数 $Z(l,\ r,\ z)$。

探索之字形的神奇魔力，实现上述操作。

The first line contains integer n (1 ≤ n ≤ 105) — The number of elements in array a. The second line contains n space-separated integers: _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) — the elements of the array.

The third line contains integer m (1 ≤ m ≤ 105) — 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 ≤ 109) — 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.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 数组 $a$ 的元素个数。
第二行包含 $n$ 个以空格分隔的整数：$a_1,\,a_2,\,\dots,\,a_n$（$1 \leq a_i \leq 10^9$）—— 数组的元素。

第三行包含一个整数 $m$（$1 \leq m \leq 10^5$）—— 操作的个数。接下来的 $m$ 行描述了这些操作。每行操作的描述以一个整数 $t_i$（$1 \leq t_i \leq 2$）开头——表示操作类型。

• 若 $t_i = 1$（赋值操作），则该行随后跟两个以空格分隔的整数：$p_i,\,v_i$（$1 \leq p_i \leq n$；$1 \leq v_i \leq 10^9$）—— 赋值操作的参数。
• 若 $t_i = 2$（Zigzag 操作），则该行随后跟三个以空格分隔的整数：$l_i,\,r_i,\,z_i$（$1 \leq l_i \leq r_i \leq n$；$2 \leq z_i \leq 6$）—— Zigzag 操作的参数。

你需要按照输入中给出的顺序依次执行这些操作。

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.

对于每次之字形（Zigzag）操作，请在单独一行中输出该之字形函数的计算结果。请按照输入中给出之字形函数的顺序输出其对应的值。

请注意：在 C++ 中，请勿使用 %lld 说明符读取或写入 64 位整数。推荐使用 cin/cout 流，或使用 %I64d 说明符。

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.

样例测试说明：

• 第一次操作的结果为 $Z(2, 3, 2) = 3·1 + 1·2 = 5$。
• 第二次操作的结果为 $Z(1, 5, 3) = 2·1 + 3·2 + 1·3 + 5·2 + 5·1 = 26$。
• 第三次操作后，数组 $a$ 变为 $2, 3, 5, 5, 5$。
• 第四次操作的结果为 $Z(1, 5, 3) = 2·1 + 3·2 + 5·3 + 5·2 + 5·1 = 38$。