3天了qwq

---

题目描述

一天，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$