背景

ZLY的船只数总是在变化
ZLY需要清点一下

描述

给出一个整数序列\(A_1\),\(A_2\),...,\(A_N\)
要求支持区间加，维护区间和

输入

第一行两个整数N,M
第二行N个整数，第i个为\(A_i\)
接下来M行一行一个命令
Add l r d 表示区间[l,r]内每个数增加d
Ask l r 表示询问区间[l,r]内各数值的和

输出

对每个Ask，输出一行一个整数为所要求的和

样例

输入

10 10
1 2 3 4 6 9 8 7 5 5
Add 2 6 3
Ask 1 5
Ask 2 9
Add 2 9 -3
Add 1 1 -2
Ask 1 10
Ask 5 8
Ask 3 4
Add 2 8 15
Ask 6 10

输出

28
59
39
24
7
70

范围

20% N,M<=10
80% N,M<=1000
100% 1<=N<=\(10^5\) 1<=M<=\(10^6\) |\(A_i\)|<=\(10^5\) 1<=l<=r<=N

限制

3s
1536K