Po eliminacjach do reprezentacji prowincji White pogrążyła się w długim okresie rozczarowania. Nie potrafiła dostrzec żadnej nadziei w swoich wynikach. Mimo to White kontynuowała ostatnie treningi przed NOI. Oprócz regularnych ćwiczeń zaczęła również zgłębiać tematy, których nigdy wcześniej nie miała okazji poznać podczas swojej przygody z OI — mając nadzieję, że przed pożegnaniem nie pozostanie już żaden żal.

Odrzucając błądzące myśli, White nagle skupiła się na zadaniu przed sobą, prostym i nudnym zadaniu na struktury danych —

White ma ciąg $n$ liczb całkowitych $a_1, a_2, \dots, a_n$. Wykona na tym ciągu $q$ operacji. Każda operacja jest jednego z trzech poniższych typów:

• 1 l r v — Dodaj $v$ do każdego elementu w przedziale $[l, r]$.
• 2 l r v — Przypisz każdemu elementowi w przedziale $[l, r]$ wartość $v$.
• 3 l r — Zapytaj o wartość $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ modulo $2^{64}$.

Twoim zadaniem jest zasymulowanie wszystkich operacji i wypisanie wyników wszystkich zapytań.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n, q$ ($1 \le n, q \le 2 \times 10^5$), oznaczające liczbę elementów oraz liczbę operacji.

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$), oznaczających początkowe elementy.

Każdy z kolejnych $q$ wierszy opisuje operację w jednym z trzech formatów:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), oznaczający operację dodawania.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), oznaczający operację przypisania.
• 3 l r ($1 \le l \le r \le n$), oznaczający operację zapytania.

Gwarantowane jest, że przez cały proces dla każdego $1 \le i \le n$ zachodzi $0 \le a_i \le 10^9$.

Wyjście

Dla każdej operacji zapytania wypisz w osobnym wierszu jedną liczbę całkowitą — wynik zapytania modulo $2^{64}$.

Przykłady

Wejście

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

Wyjście

35
39
40
34
177
120

Wejście

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

Wyjście

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

Uwaga

W pierwszym przypadku testowym:

Początkowy ciąg to 2 3 5 4 1. Po trzeciej operacji staje się on równy 2 3 2 2 1, a po szóstej operacji staje się równy 7 8 7 7 6.

Dla pierwszego zapytania odpowiedzią jest $\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$.

Dla drugiego zapytania odpowiedzią jest $\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$.