4720 - 提高：线段树:【例 2】A Simple Problem with Integers
Time Limit : 1 秒
Memory Limit : 512 MB
Input
第一行包含 2 个正整数 n,q，表示数列长度和询问个数。保证 1≤n,q≤10^6 。
第二行 n 个整数 a[1],a[2],…,a[n]，表示初始数列。保证 ∣∣a[i]∣≤10^6 。
接下来 q 行，每行一个操作，为以下两种之一：
Output
对于每个 2 l r 操作，输出一行，每行有一个整数，表示所求的结果。
Examples
Input
5 10 2 6 6 1 1 2 1 4 1 2 5 10 2 1 3 2 2 3 1 2 2 8 1 2 3 7 1 4 4 10 2 1 2 1 4 5 6 2 3 4
Output
15 34 32 33 50
Hint
数据范围与提示：
对于所有数据，1≤n,q≤10^6,∣a[i]∣≤10^6,1≤l≤r≤n,∣x∣≤10^6 。