题目描述

给出一个长度为 $n$ 的序列 $a$，有 $m$ 次操作，格式如下：

1 x y k 对于所有满足 $(i-1) \bmod x \le y$ 的 $i$，将 $a_i$ 的值加 $k$。

2 l r 求 $\sum\limits_{i=l}^r a_i$ 。

数组下标从 $1$ 开始。

输入格式

第一行两个正整数 $n,m$。

接下来一行 $n$ 个整数表示 $a_i$ 的值。

然后 $m$ 行，每行表示一个操作。

输出格式

对于所有的 $2$ 操作，输出答案。

样例 #1

样例输入 #1

6 7
1 1 4 5 1 4
2 1 5
1 1 4 5
2 1 5
1 3 2 1
2 4 6
1 4 2 2
2 1 6

样例输出 #1

12
37
28
62

提示

对于 $100\%$ 的数据，满足：

• $1\le n,m\le 2\times 10^5$
• $1\le x,y \le n$
• $1\le a_i,k\le 10^9$。