Дерево Фенвика
Зміна на відрізку High
Задано набір з n цілих чисел a[0], a[1], ..., a[n-1]. На початку усі ці числа рівні 0. Далі поступають запити на зміну та виведення. Для запиту на зміну задаються три числа l, r, d. За цим запитом до кожного з елементів a[i] (l ≤ i ≤ r) необхідно додати значення d. Для запиту на виведення задається одне число i. За цим запитом потрібно вивести поточне значення елемента a[i].
Вхідні дані
У першому рядку задано два цілих числа n і m (1 ≤ n ≤ 10^6, 0 ≤ m ≤ 10^6), які позначають кількість елементів та кількість запитів відповідно. У наступних m рядках задаються запити. Запит на зміну задається рядком виду "A l r d" (0 ≤ l ≤ r < n, |d| ≤ 10^3), запит на виведення - рядком "Q i" (0 ≤ i < n). Усі числа цілі.
Вихідні дані
Для кожного запита на виведення виведіть у окремому рядку поточне значення відповідного елементу.
Приклад
10 6 A 3 7 1 Q 4 A 1 5 2 Q 4 Q 1 Q 6
1 3 2 1