Dopo la selezione della squadra provinciale, White cadde in un lungo periodo di delusione. Non riusciva a trovare alcuna speranza nei suoi risultati. Nonostante ciò, White continuò il suo allenamento finale prima delle NOI. Oltre all'allenamento regolare, iniziò anche a esplorare argomenti che non aveva mai avuto l'opportunità di imparare durante i suoi giorni nelle OI — sperando che, prima di dire addio, non ci sarebbero stati più rimpianti.

Scacciando i pensieri vaganti, White si concentrò improvvisamente su un problema davanti a sé, un semplice e noioso problema di strutture dati —

White ha una sequenza di $n$ interi $a_1, a_2, \dots, a_n$. Eseguirà $q$ operazioni su questa sequenza. Ciascuna operazione è di uno dei seguenti tre tipi:

• 1 l r v — Aggiungi $v$ a ciascun elemento nell'intervallo $[l, r]$.
• 2 l r v — Assegna a ciascun elemento nell'intervallo $[l, r]$ il valore $v$.
• 3 l r — Chiedi il valore di $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ modulo $2^{64}$.

Il tuo compito è simulare tutte le operazioni e stampare i risultati di tutte le query.

Input

La prima riga dell'input contiene due interi $n, q$ ($1 \le n, q \le 2 \times 10^5$), che rappresentano il numero di elementi e il numero di operazioni.

La seconda riga contiene $n$ interi $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$), che rappresentano gli elementi iniziali.

Ciascuna delle successive $q$ righe descrive un'operazione, in uno dei tre formati:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), che rappresenta l'operazione di somma.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), che rappresenta l'operazione di assegnamento.
• 3 l r ($1 \le l \le r \le n$), che rappresenta l'operazione di query.

È garantito che $0 \le a_i \le 10^9$ per ogni $1 \le i \le n$ durante l'intero processo.

Output

Per ciascuna operazione di query, stampa un intero su una singola riga — il risultato della query modulo $2^{64}$.

Esempi

Input

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

Output

35
39
40
34
177
120

Input

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

Output

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

Note

Nel primo caso di test:

La sequenza originale è 2 3 5 4 1. Dopo la terza operazione diventa 2 3 2 2 1, e dopo la sesta operazione diventa 7 8 7 7 6.

Per la prima query, la risposta è $\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$.

Per la seconda query, la risposta è $\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$.