e-olymp
Змагання

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

Зміна на відрізку Junior

Задано набір зN цілих чисел a0, a1, ..., aN-1. На початку усі ці числа рівні0. Далі поступають запити на зміну та виведення. Для запиту на зміну задаються три числаl, r, d. За цим запитом до кожного з елементівai (lir) необхідно додати значенняd. Для запиту на виведення задається одне числоi. За цим запитом потрібно вивести поточне значення елементаai.

Вхідні дані

У першому рядку вхідного файлу задано три цілих числаN, MA і MQ, які позначають кількість елементів, кількість запитів на зміну і на виведення відповідно. У наступних MA+MQ рядках задаються запити. Запит на зміну задається рядком виду "A l r d", запит на виведення – рядком "Q i".

Усі числа цілі. 1N106, 0MA, MQ106, 0lr < N, 0i < N, |d|103. Гарантується, що по меншій мірі одне з чисел N, MA або MQ не буде перевищувати 50.

Вихідні дані

Для кожного запиту на виведення виведіть у окремому рядку поточне значення відповідного елементу.

Ліміт часу 1 секунда
Ліміт використання пам'яті 8 MiB
Вхідні дані
10 2 4
A 3 7 1
Q 4
A 1 5 2
Q 4
Q 1
Q 6
Вихідні дані
1
3
2
1
Автор Неспірний В.М.