问题描述

有一个数组里有n个整数，现在有两个操作

1. $o,x,y,z$，区间$x,y$加上$z$
2. $o,x,y$，查询$x,y$的和

输入格式

• 第一行整数n，m，表示n个数，m个询问
• 第二个n个整数
• 接下来m个询问

输出格式

全部过河的最少耗时。

输入样例 1

5 2
2 6 9 2 7
1 1 3 1
2 3 5

输出样例 1

19

数据范围

• $1 \leqslant n \leqslant 100000$
• $-1000 \leqslant a_i \leqslant 1000$