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

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

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

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

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

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

10
613 263 312 670 216 142 976 355 488 370
10
s 2 7
s 4 8
u 7 969
u 1 558
s 2 7
u 2 731
s 4 9
s 1 3
u 8 76
u 5 377

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

2579 2359 2572 2840 1601