Nach der Auswahl für das Provinzteam fiel White in eine lange Phase der Enttäuschung. Sie konnte in ihren Ergebnissen keinerlei Hoffnung finden. Trotzdem setzte White ihr abschließendes Training vor der NOI fort. Neben ihrem regulären Training begann sie auch, Themen zu erkunden, die sie während ihrer OI-Zeit nie hatte lernen können — in der Hoffnung, dass es vor dem Abschied keine Reue mehr geben würde.

White schüttelte ihre abschweifenden Gedanken ab und konzentrierte sich plötzlich auf ein Problem vor ihr, ein schlichtes und langweiliges Datenstrukturproblem —

White hat eine Folge von $n$ ganzen Zahlen $a_1, a_2, \dots, a_n$. Sie führt $q$ Operationen auf dieser Folge aus. Jede Operation gehört zu einem der folgenden drei Typen:

• 1 l r v — Addiere $v$ zu jedem Element im Intervall $[l, r]$.
• 2 l r v — Weise jedem Element im Intervall $[l, r]$ den Wert $v$ zu.
• 3 l r — Frage den Wert $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ modulo $2^{64}$ ab.

Deine Aufgabe ist es, alle Operationen zu simulieren und die Ergebnisse aller Abfragen auszugeben.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen $n, q$ ($1 \le n, q \le 2 \times 10^5$), die die Anzahl der Elemente und die Anzahl der Operationen darstellen.

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$), die die anfänglichen Elemente darstellen.

Jede der nächsten $q$ Zeilen beschreibt eine Operation in einem der drei Formate:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), steht für die Additionsoperation.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), steht für die Zuweisungsoperation.
• 3 l r ($1 \le l \le r \le n$), steht für die Abfrageoperation.

Es wird garantiert, dass während des gesamten Prozesses für jedes $1 \le i \le n$ stets $0 \le a_i \le 10^9$ gilt.

Ausgabe

Gib für jede Abfrageoperation in einer eigenen Zeile eine ganze Zahl aus — das Ergebnis der Abfrage modulo $2^{64}$.

Beispiele

Eingabe

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

Ausgabe

35
39
40
34
177
120

Eingabe

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

Ausgabe

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

Hinweis

Im ersten Testfall:

Die ursprüngliche Folge lautet 2 3 5 4 1. Nach der dritten Operation wird sie zu 2 3 2 2 1, und nach der sechsten Operation wird sie zu 7 8 7 7 6.

Für die erste Abfrage lautet die Antwort $\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$.

Für die zweite Abfrage lautet die Antwort $\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$.