Il y a une séquence $A_0, A_1, \ldots, A_{n-1}$ de longueur $n$. Écrivez un programme pour exécuter les requêtes suivantes :

• 1 l r c : Ajouter $c$ à tous les $A_i$ de l’intervalle $l \le i \le r$.
• 2 l r d : Remplacer tous les $A_i$ de l’intervalle $l \le i \le r$ par $\lfloor A_i/d \rfloor$.
• 3 l r : Afficher le minimum de tous les $A_i$ de l’intervalle $l \le i \le r$.
• 4 l r : Afficher la somme de tous les $A_i$ de l’intervalle $l \le i \le r$.

où $\lfloor x \rfloor$ désigne le plus grand entier $y$ tel que $y \le x$ (par exemple, $\lfloor -2.5 \rfloor = -3$, $\lfloor -7 \rfloor = -7$).

Entrée

La première ligne contient deux entiers $n$ et $q$ ($1 \le n, q \le 100\,000$), indiquant la longueur de la séquence et le nombre de requêtes.

La deuxième ligne contient $n$ entiers $A_0, A_1, \ldots, A_{n-1}$ ($-10^9 \le A_i \le 10^9$).

Chacune des $q$ lignes suivantes contient une requête ($0 \le l \le r \le n-1$, $-10^4 \le c \le 10^4$, $2 \le d \le 10^9$).

Sortie

Lorsqu’une requête de type 3 ou de type 4 est rencontrée, afficher une réponse par ligne.

Exemples

Entrée 1

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9

Sortie 1

-2
-2
-2
-2
0
1
1