1.1.5　序列变换

【上机练习】序列变换（change）

对一个由n个整数构成的序列有以下两种操作。

操作1为“1 x y”，表示所有a[kx]（k为正整数，kx≤n）的值都加上y（|y|≤1000000）。

操作2为“2 i”，表示输出a[i]（i≤n，操作数不超过10000条）的值。 

【输入格式】

第1行为两个整数n和m（n≤1000000，m≤100000），表示有n个数，m条操作。

第2行为n个数（这些数的绝对值小于或等于1000000）。 

随后m行为m条操作。

【输出格式】

输出若干行，每行对应完成一次操作2后输出的值。

【输入样例】

5 4

6 9 9 8 1 

2 4

1 2 5

1 3 1

2 4

【输出样例】

8

13

【算法分析】

因为数据规模过大，在执行操作1时，如果将所有a[kx] 逐个加上y，显然会超时，所以需要考虑更优的算法。