题目描述

给定一个大小为n个数组a，q次操作。

每次操作分为下面两种：

"1 l, r v"：给区间[l, r]中的数组加上v。

"2 l r"：查询区间[l, r]中数字的和。

对于每次2操作，输出结果。

输入格式

第一行两个整数n, q。(1 \le n, q \le 2 \times 10^5)

第二行n个整数表示数组a。(-10^5 \le a_i \le 10^5)

接下来q行，每行一个操作。(1 \le l \le r \le n, -10^5 \le v \le 10^5)

输出格式

对于每次2操作，在一行内输出结果。

样例输入1

5 4
1 2 3 4 5
1 1 3 1
2 1 2
1 4 5 2
2 3 4

样例输出1

5
10