Fenwick Tree (BIT)

Problem statement

A donation board tracks a running total across its numbered collection boxes. New donations or corrections add a signed amount to one box, and the operator frequently asks for the total from the first box through a chosen box. Your task Implement a Fenwick tree supporting add index delta and prefix index. add changes the stored value by delta; prefix returns the sum of positions 0 through index inclusive. Important details The initial array may contain negative values. An add is an increment, not an assignment. Use zero-based indices in the input and translate them consistently to the internal Fenwick representation. Each operation must take O(log n) time. Worked example For [2, 3, 4], prefix 1 returns 5. After add 0 -1, prefix 2 returns 8 because the values are now [1, 3, 4].

Input format

First line: n q. Next line: n values. Next q lines: add index delta or prefix index.

Output format

Print one answer per prefix query, or EMPTY if there are none.

Constraints

1 <= n, q <= 100000; -1000000000 <= initial values, delta <= 1000000000; indices are valid; use 64-bit sums.

Sample input

3 3
2 3 4
prefix 1
add 0 -1
prefix 2

Sample output

5
8