Changing on a Segment (High)
n integers a[0], a[1], ..., a[n-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 a[i] (l ≤ i ≤ r) the value d. The print query contains one integer i. You must print the current value a[i].
Input
The first line contains two integers n and m (1 ≤ n ≤ 10^6, 0 ≤ m ≤ 10^6) - 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| ≤ 10^3), 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.