eolymp
bolt
Try our new interface for solving problems
Problems

Changing on a Segment (High)

Changing on a Segment (High)

Time limit 1 second
Memory limit 128 MiB

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

Input data

The first line contains two integers n and m (1n10^6, 0m10^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" (0lr < n, |d| ≤ 10^3), the print query is given with the line "Q i" (0i < n). All values are integers.

Output data

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

Examples

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