Une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$ est donnée. Écrire un programme pour traiter les requêtes suivantes :

• 1 i v : Affecter la valeur $v$ à $A_i$.
• 2 k i j : Lorsque la $k$-ième requête de type 1 a été appliquée, afficher la somme de $A_i, A_{i+1}, \ldots, A_j$.

Entrée

La première ligne contient la longueur $N$ de la séquence ($1 \le N \le 100\,000$).

La deuxième ligne contient $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 1\,000\,000$).

La troisième ligne contient le nombre de requêtes $M$ ($1 \le M \le 100\,000$).

Les $M$ lignes suivantes contiennent chacune une requête. Pour les requêtes de type 1, $1 \le i \le N$, $1 \le v \le 1\,000\,000$ ; pour les requêtes de type 2, $1 \le i \le j \le N$, et $0 \le k \le$ (le nombre de requêtes de type 1 données jusqu'à ce point).

Tous les nombres en entrée sont des entiers.

Sortie

Pour chaque requête de type 2, afficher sa somme.

Exemples

Entrée 1

5
1 2 3 4 5
7
1 2 5
2 0 1 3
2 1 1 3
1 4 2
2 0 2 5
2 1 2 5
2 2 2 5

Sortie 1

6
9
14
17
15