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

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

В першому рядку число \(N\) - розмір масиву (\(1 \le N \le 2*10^5\))
В другому рядку \(N\) чисел - елементи масиву (\(0 \le Ai \le 100\))
В третьому рядку число \(M\) - кількість запитів (\(1 \le N \le 2*10^5\))
Кожен з наступних \(M\) рядків описує запит. Спочатку вводиться одна літера, що кодує тип запиту (m - обчислити максимум на префіксі, a - додати значення до елемента).
Вслід за літерою m вводиться одне число \(X\) (необхідно знайти максимум в масиві на відрізку \([1..X]\) ).
Вслід за літерою a вводиться число \(POS\) - номер елемента, та число \(VAL\) яке додається його значення. (\(0 \le VAL \le 100\))

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

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

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

5
1 7 4 9 3
4
m 3
a 5 10
a 1 20
m 5

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

7
21