Après la sélection de l'équipe provinciale, White est tombée dans une longue période de déception. Elle ne voyait aucun espoir dans ses résultats. Malgré cela, White a poursuivi son entraînement final avant la NOI. En plus de son entraînement régulier, elle a également commencé à explorer des sujets qu'elle n'avait jamais eu l'occasion d'apprendre pendant ses années d'OI — espérant qu'avant de dire adieu, il n'y aurait plus de regrets.

Chassant ses pensées vagabondes, White s'est soudainement concentrée sur un problème devant elle, un problème de structure de données simple et ennuyeux —

White dispose d'une suite de $n$ entiers $a_1, a_2, \dots, a_n$. Elle va effectuer $q$ opérations sur cette suite. Chaque opération est de l'un des trois types suivants :

• 1 l r v — Ajouter $v$ à chaque élément de l'intervalle $[l, r]$.
• 2 l r v — Affecter la valeur $v$ à chaque élément de l'intervalle $[l, r]$.
• 3 l r — Demander la valeur de $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ modulo $2^{64}$.

Votre tâche consiste à simuler toutes les opérations et à afficher les résultats de toutes les requêtes.

Entrée

La première ligne de l'entrée contient deux entiers $n, q$ ($1 \le n, q \le 2 \times 10^5$), représentant le nombre d'éléments et le nombre d'opérations.

La deuxième ligne contient $n$ entiers $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$), représentant les éléments initiaux.

Chacune des $q$ lignes suivantes décrit une opération, sous l'un des trois formats :

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), représentant l'opération d'ajout.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), représentant l'opération d'affectation.
• 3 l r ($1 \le l \le r \le n$), représentant l'opération de requête.

Il est garanti que $0 \le a_i \le 10^9$ pour chaque $1 \le i \le n$ tout au long du processus.

Sortie

Pour chaque opération de requête, affichez un entier sur une seule ligne — le résultat de la requête modulo $2^{64}$.

Exemples

Entrée

5 8
2 3 5 4 1
3 1 5
3 2 4
2 4 5 2
3 1 5
3 2 4
1 1 2 5
3 1 5
3 2 4

Sortie

35
39
40
34
177
120

Entrée

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

Sortie

40
156
270
120
1202
270
118
831
80
33
61
80
40
156
270

Note

Dans le premier cas de test :

La suite initiale est 2 3 5 4 1. Après la troisième opération, elle devient 2 3 2 2 1, et après la sixième opération, elle devient 7 8 7 7 6.

Pour la première requête, la réponse est $\sum_{i=1}^5 (\min_{j=1}^i a_j) \times (\max_{j=1}^i a_j) = 2 \times 2 + 2 \times 3 + 2 \times 5 + 2 \times 5 + 1 \times 5 = 35$.

Pour la deuxième requête, la réponse est $\sum_{i=2}^4 (\min_{j=2}^i a_j) \times (\max_{j=2}^i a_j) = 3 \times 3 + 3 \times 5 + 3 \times 5 = 39$.