CF228D Zigzag

宫廷巫师 Zigzag 想要成为一名著名的数学家。为此，他需要他自己的定理，正如柯西定理，或者他的和，正如闵可夫斯基和。但他最想要的是拥有他自己的序列，正如斐波那契数列，和他的函数，正如欧拉函数。 zigzag 因子为 $z$ 的 Zigzag 序列是一个无穷序列 $S_i^z$（$i\ge 1; z\ge 2$），它的定义如下： - $S_i^z = 2$，当 $(i \bmod 2(z - 1)) = 0$ 时； - $S_i^z = (i \bmod 2(z - 1))$，当 $0 < (i \bmod 2(z - 1)) \le z$ 时； - $S_i^z = 2z - (i \bmod 2(z - 1))$，当 $(i \bmod 2(z - 1)) > z$ 时。 运算 $x \bmod y$ 表示取数 $x$ 除以数 $y$ 的余数。例如，序列 $S_i^3$（zigzag 因子为 $3$）的开头如下所示：$1, 2, 3, 2, 1, 2, 3, 2, 1$。 给定一个由 $n$ 个整数组成的数组 $a$，将数组中编号为 $i$（$1 \le i \le n$) 的元素记为 $a_i$。Zigzag 函数是函数 $Z(l, r, z) = \sum_{i=l}^{r} a_i \cdot S_{i-l+1}^z$，其中 $l, r, z$ 满足不等式 $1 \le l \le r \le n, z \ge 2$。 为了更好地熟悉 Zigzag 序列和 Zigzag 函数，巫师要求你在给定的数组 $a$ 上实现以下操作。 1. 赋值操作。操作参数是 $(p, v)$。该操作表示将值 $v$ 赋给数组的第 $p$ 个元素。应用该操作后，数组元素 $a_p$ 的值等于 $v$。 2. Zigzag 操作。操作参数是 $(l, r, z)$。该操作表示计算 Zigzag 函数 $Z(l, r, z)$。 探索 zigzag 的神奇力量，实现所描述的操作。

第一行包含整数 $n$（$1 \le n \le 10^5$）——数组 $a$ 的元素个数。第二行包含 $n$ 个以空格分隔的整数：$a_1, a_2, \cdots, a_n$（$1 \le a_i \le 10^9$）——数组的元素。 第三行包含整数 $m$（$1 \le m \le 10^5$）——操作的数量。接下来的 $m$ 行包含操作的描述。操作的描述以整数 $t_i$（$1 \le t_i \le 2$）开头——操作类型。 - 如果 $t_i = 1$（赋值操作），那么该行接下来是两个以空格分隔的整数：$p_i, v_i$（$1 \le p_i \le n; 1 \le v_i \le 10^9$）——赋值操作的参数。 - 如果 $t_i = 2$（Zigzag 操作），那么该行接下来是三个以空格分隔的整数：$l_i, r_i, z_i$（$1 \le l_i \le r_i \le n; 2 \le z_i \le 6$）——Zigzag 操作的参数。 你应该按照输入中给出的顺序执行操作。

对于每个 Zigzag 操作，将计算出的 Zigzag 函数值打印在单独的一行上。按照输入中给出的顺序打印 Zigzag 函数的值。

样例解释： - 第一次操作的结果是 $Z(2, 3, 2) = 3\cdot 1 + 1\cdot 2 = 5$。 - 第二次操作的结果是 $Z(1, 5, 3) = 2\cdot 1 + 3\cdot 2 + 1\cdot 3 + 5\cdot 2 + 5\cdot 1 = 26$。 - 第三次操作后，数组 $a$ 变为 $2, 3, 5, 5, 5$。 - 第四次操作的结果是 $Z(1, 5, 3) = 2\cdot 1 + 3\cdot 2 + 5\cdot 3 + 5\cdot 2 + 5\cdot 1 = 38$。