Une séquence $A_0, A_1, \ldots, A_{N-1}$ de longueur $N$ est donnée. Écrivez un programme qui traite les requêtes suivantes ($0 \le A_i < 2^{32}$) :

• 1 p v : Insérer $v$ avant $A_p$. Si $p$ est égal à la longueur de $A$, il est inséré à la fin. ($0 \le p \le$ longueur de $A$, $0 \le v < 2^{32}$)
• 2 p : Supprimer $A_p$. ($0 \le p <$ longueur de $A$)
• 3 p v : Remplacer $A_p$ par $v$. ($0 \le p <$ longueur de $A$, $0 \le v < 2^{32}$)
• 4 l r k : Calculer $(\sum A_i \times (i - l + 1)^k) \bmod 2^{32}$ et l'afficher. ($0 \le k \le 10$)

Entrée

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

La deuxième ligne contient $A_0, A_1, \ldots, A_{N-1}$.

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.

Sortie

Pour chaque requête, affichez la réponse sur une ligne séparée.

Exemples

Entrée 1

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

Sortie 1

6
26
40
4