Реалізуйте стурктуру даних, що дозволяє ефективно додавати число до елемента масиву та знаходити суму на відрізку.

Формат вхідних даних

В першому рядку число \(N\) (\(1 \le N \le 10^5\))
В другому рядку \(N\) чисел - елементи масиву (\(0 \le Ai \le 10^5\))
В третьому рядку число \(M\) - кількість запитів (\(1 \le M \le 30000\))
Кожен з наступних \(M\) рядків описує запит. Спочатку вводиться одна літера, що кодує тип запиту (s - обчислити суму, u - додати до значення елемента задане число).
Вслід за літерою s вводяться два числа - номер лівої та правої границі відрізка для якого необхідно обчилити суму.
Вслід за літерою u вводяться два числа - номер елемента і число яке необхідно до цього елемента додати.

Формат вихідних даних

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

Приклад вхідних даних

10
1 2 3 4 5 6 7 8 9 10
10
s 2 7
s 4 8
u 7 10
u 1 20
s 2 7
u 2 30
s 4 9
s 1 3
u 8 1
u 5 2

Приклад вихідних даних

27 30 37 49 56