题目描述

给定n个数列，规定有两种操作，一是修改某个元素，二是求子数列[a,b]的连续和。数列的元素个数最多是10万个，询问操作最多10万次。

输入

第一行2高整数n，m（n表示输入n个数，m表示有m个操作）。保证1≤n,m≤10^6

第二行输入n个数列。

接下来m行，每行有三个数k，a，b（k=2，表示求子数列[a,b]的和；k=1，表示第a个数加b）。

输出

输出若干行数字，表示k=2时，对应的子数列[a,b]的连续和。

保证1≤a≤b≤n，|b|≤10^6

样例

3 2
1 2 3
1 2 0
2 1 3

6