#8. 简化版树状数组(?)

简化版树状数组(?)

背景

树状数组是经典的数据结构,小P需要你实现一个简化版树状数组(?)

题目描述

如题,已知一个数列,你需要进行下面两种操作:

  • 将某一个数加上 xx (单点修改)

  • 求出某个数的值 (单点查询)

输入格式

第一行包含两个正整数 n,mn,m,分别表示该数列数字的个数和操作的总个数。 1n,m1051\leq n,m\leq 10^5

第二行包含 nn 个用空格分隔的整数,其中第 ii 个数字表示数列第 ii 项的初始值。 105ai105-10^5\leq a_i\leq 10^5 .

接下来 mm 行每行包含 33 或者 22 个整数,表示一个操作,具体如下:

  • 1 x k 含义:将第 xx 个数加上 kk

  • 2 x 含义:输出第 xx 个数的值

其中1xn,105k1051\leq x\leq n,-10^5\leq k\leq 10^5

输出格式

输出包含若干行整数,即为所有操作 22 的结果。

Samples

1 3
2
2 1
1 1 1
2 1
2
3