Дерево Фенвика

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 (lir) the value d. The print query contains one integer i. You must print the current value ai.


The first line contains two integers n and m (1n106, 0m106) - 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**" (0lr < n, |d| ≤ 103), the print query is given with the line "**Q i**" (0i < n). All values are integers.


For each print query output in a separate line the current value of corresponding element.

Time limit 1 second
Memory limit 128 MiB
Input example #1
10 6
A 3 7 1
Q 4
A 1 5 2
Q 4
Q 1
Q 6
Output example #1
Author Неспирный В.Н.