给定长度为 $N$ 的数列 $A$，然后输入 $M$ 行操作指令。

第一类指令形如 C l r d，表示把数列中第 $l \sim r$ 个数都加 $d$。

第二类指令形如 Q x，表示询问数列中第 $x$ 个数的值。

对于每个询问，输出一个整数表示答案。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数 $A[i]$。

接下来 $M$ 行表示 $M$ 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

$1 \le N,M \le 10^5$,
$|d| \le 10000$,
$|A[i]| \le 10^9$

输入样例：

10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2

输出样例：

4
1
2
5

#include <iostream>
#include <algorithm>

using namespace std;

template<typename T>
class BIT {
private:
    vector<T> tree;
    int n;

    // 获取最低位的 1 所代表的值
    int lowbit(int x) {
        return x & -x;
    }

public:
    BIT(int size) : n(size + 1) {
        tree.resize(n);
    }

    // 单点更新
    void update(int idx, T val) {
        while (idx < n) {
            tree[idx] += val;
            idx += lowbit(idx);
        }
    }

    // 前缀和查询
    T query(int idx) {
        T sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= lowbit(idx);
        }
        return sum;
    }

    // // 区间查询
    // T queryRange(int left, int right) {
    //     return query(right) - query(left - 1);
    // }
};


int main()
{
    int n, m;
    cin >> n >> m;
    BIT<int> bit(n + 1);
    for (int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        bit.update(i, x), bit.update(i + 1, - x);
    }
    while (m --)
    {
        char op;
        cin >> op;
        if (op == 'C')
        {
            int l, r, d;
            cin >> l >> r >> d;
            bit.update(l, d), bit.update(r + 1, - d);
        }
        else
        {
            int x;
            cin >> x;
            cout << bit.query(x) << '\n';
        }
    }

    return 0;
}