6905: 华华开始学信息学
[Creator : ]
Description
因为上次在月月面前丢人了，所以华华决定开始学信息学。十分钟后，他就开始学树状数组了。这是一道树状数组的入门题：
给定一个长度为 $N$ 的序列 $A$，所有元素初值为 $0$。接下来有 $M$次操作或询问：
操作：输入格式：1 D K，对于所有满足 $1\le i\le N$ 且 $i\equiv0(\bmod D)$ 的 $i$，将 $A_i$ 加上 $K$。
询问：输入格式：2 L R，询问区间和，即 $\sum_{i=L}^{R}A_i$。
华华是个 newbie，怎么可能会这样的题？不过你应该会吧。
给定一个长度为 $N$ 的序列 $A$，所有元素初值为 $0$。接下来有 $M$ 次操作或询问：华华很快就学会了树状数组并通过了这道题。月月也很喜欢树状数组，于是给华华出了一道进阶题：
操作：输入格式：1 D K，将 $A_D$ 加上 $K$。
询问：输入格式：2 L R，询问区间和，即 $\sum_{i=L}^{R}A_i$。
给定一个长度为 $N$ 的序列 $A$，所有元素初值为 $0$。接下来有 $M$次操作或询问：
操作：输入格式：1 D K，对于所有满足 $1\le i\le N$ 且 $i\equiv0(\bmod D)$ 的 $i$，将 $A_i$ 加上 $K$。
询问：输入格式：2 L R，询问区间和，即 $\sum_{i=L}^{R}A_i$。
华华是个 newbie，怎么可能会这样的题？不过你应该会吧。
Input
第一行两个正整数 $N, M$ 表示序列的长度和操作询问的总次数。
接下来 $M$ 行每行三个正整数，表示一个操作或询问。
接下来 $M$ 行每行三个正整数，表示一个操作或询问。
Output
对于每个询问，输出一个非负整数表示答案。
Constraints
$1≤N,M≤10^5,\ 1\le D\le N,\ 1\le L\le R\le N,\ 1\le K \le 10^8$
Sample 1 Input
10 6
1 1 1
2 4 6
1 3 2
2 5 7
1 6 10
2 1 10
Sample 1 Output
3
5
26