U527000 美穗的花店

在像素塔的中之层，有一片漫漫花海，而美穗的花店，也深居其中…… _“先生买一朵花吧，你看多可爱啊！” ——美穗_ 

美穗的花店售卖着各式各样的mope花，因为这些花儿样貌可（kǒng）爱（bù），常常受到人们的青睐，吸引人们购买。这不，今天就有一大批顾客来到美穗的花店来购买 mope 花。可统计 mope 花售出的数量，却成了美穗一大难题。现在，请你帮助她计算售卖 mope 花的数量，完成相应的操作。 美穗售卖的 mope 花共有 $n$ 种 $(1\leq n\leq 2\times10^5)$ , 同时共有 $m$ 次操作 $(1\leq m\leq 10^5)$ ，分别为： - 一位顾客购买种类 $x$ 至种类 $y$ 的 mope 花，每种购买 $k$ 朵 $(1\leq x\leq y \leq n ,1\leq k\leq 10^3 )$ ； - 求出种类 $x$ 至种类 $y$ 的 mope 花所售卖出的总数 $(1\leq x\leq y \leq n )$ 。 同时，在前一天，几位顾客预定了几株不同种类的 mope 花（没错，像素塔里可以预订 mope 花，而且这些 mope 花算入今日的售卖数）。由于美穗现在心情非常不好，她要求你在 $1$ 秒内完成她你的任务，~~否则她会拿出有毒的 mope 花把你吃掉。~~

第 $1$ 行输入两个正整数 $n,m$ ,含义见题目描述。 第 $2$ 行共有 $n$ 个数 $a_i $ $(1\leq a_i \leq 10^3)$ ，表示前一天顾客预定第 $i$ 种 mope 花的数量。 第 $3$ 行至第 $m+2$ 行共有 $m$ 次操作，每一行第一个数 $opt$，表示操作方案。 - 若 $opt=1$，则继续输入三个数 $x,y,k$，表示一位顾客购买种类 $x$ 至种类 $y$ 的 mope 花，每种购买 $k$ 朵； - 若 $opt=2$，则继续输入三个数 $x,y$，表示求出种类 $x$ 至种类 $y$ 的 mope 花所售卖出的总数 $(1\leq x\leq y \leq n )$ 。

输出包含若干行整数，每行一个整数，即为所有第二种操作的结果。保证输出的结果不大于 ${10}^{12}$ 。

（实际上就是线段树的模板） ### 样例解释 前一天顾客预定 $n$ 种 mope 花售出的数量：$1$、$5$、$4$、$2$、$3$ 第一次操作（求出 mope 花 2 至 mope 花 4 共售出的数量为 $5+4+2=11$ ） $n$ 种 mope 花售出的数量：$1$、$5$、$4$、$2$、$3$ 第二次操作（一位顾客购买 mope 花 2 至 mope 花 3 ，每种购买 $2$ 朵 ） $n$ 种 mope 花售出的数量：$1$、$7$、$6$、$2$、$3$ 第三次操作（求出 mope 花 3 至 mope 花 4 共售出的数量为 $6+2=8$ ） $n$ 种 mope 花售出的数量：$1$、$7$、$6$、$2$、$3$ 第四次操作（一位顾客购买 mope 花 1 至 mope 花 5 ，每种购买 $1$ 朵 ） $n$ 种 mope 花售出的数量：$2$、$8$、$7$、$3$、$4$ 第五次操作（求出 mope 花 1 至 mope 花 5 共售出的数量为 $2+8+7+3+4=24$ ） $n$ 种 mope 花售出的数量：$2$、$8$、$7$、$3$、$4$ ### 数据范围 对于$10\%$的数据，满足 $n,m,k\leq 100$ , $a_i \leq 10 $ 。 对于$40\%$的数据，满足 $n,m,k\leq 10^3$ , $a_i \leq 100 $ 。 对于$100\%$的数据，满足 $1\leq x\leq y \leq n\leq 2\times 10^5$ , $1\leq m\leq 10^5$ , $1\leq k,a_i\leq 10^3$ 。