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，顯然會超時，所以需要考慮更優的算法。