背景

ZLY的船只数总是在变化
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，输出一行一个整数为所要求的和

样例

输入

20 20
-10 10 90 -56 -25 -82 20 100 -4 -11 95 80 18 -45 18 67 -48 -81 -67 -30 
Ask 12 16
Ask 2 16
Add 4 16 67
Ask 7 11
Ask 11 15
Ask 5 19
Ask 2 6
Add 1 19 27
Add 6 18 -67
Ask 3 7
Ask 2 14
Ask 1 19
Ask 10 14
Ask 3 15
Add 10 14 -78
Ask 6 10
Add 5 18 -7
Add 5 19 -78
Add 13 17 -86
Ask 1 20

输出

138
275
535
501
839
138
216
675
582
272
683
80
-1536

范围

20% N,M<=1000 |\(A_i\)|<=\(10^3\)
50% N<=50000
60% N<=100000
80% N<=500000 M<=\(10^5\)
100% 1<=N<=\(10^6\) 1<=M<=\(10^6\) |\(A_i\)|<=\(10^4\) 1<=l<=r<=N

限制

3s
14848K