Дерево Фенвика
Changing on a Segment (High)
n integers a0
, a1
, ..., an-1
are given. Initially they all are 0. Then you have a list of queries to change some elements or to print one element. The change query contains three integers l, r, d. You must add to each element ai
(l ≤ i ≤ r) the value d. The print query contains one integer i. You must print the current value ai
.
Input
The first line contains two integers n and m (1 ≤ n ≤ 106
, 0 ≤ m ≤ 106
) - the number of elements and the number of queries. In the next m lines the queries are given. The change query is given with the line "**A l r d**" (0 ≤ l ≤ r < n, |d| ≤ 103
), the print query is given with the line "**Q i**" (0 ≤ i < n). All values are integers.
Output
For each print query output in a separate line the current value of corresponding element.
10 6 A 3 7 1 Q 4 A 1 5 2 Q 4 Q 1 Q 6
1 3 2 1