После отбора в сборную провинции White надолго впала в уныние. Она не видела никакой надежды в своих результатах. Несмотря на это, White продолжила свои последние тренировки перед NOI. Помимо обычных тренировок, она также начала изучать темы, до которых у неё никогда не доходили руки во времена её участия в OI — надеясь, что перед прощанием у неё больше не останется сожалений.

Отбросив блуждающие мысли, White внезапно сосредоточилась на задаче перед собой — простой и скучной задаче на структуры данных —

У White есть последовательность из $n$ целых чисел $a_1, a_2, \dots, a_n$. Она выполнит $q$ операций над этой последовательностью. Каждая операция принадлежит к одному из следующих трёх типов:

• 1 l r v — Прибавить $v$ к каждому элементу на отрезке $[l, r]$.
• 2 l r v — Присвоить каждому элементу на отрезке $[l, r]$ значение $v$.
• 3 l r — Запросить значение $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ по модулю $2^{64}$.

Ваша задача — промоделировать все операции и вывести результаты всех запросов.

Формат входных данных

Первая строка входных данных содержит два целых числа $n, q$ ($1 \le n, q \le 2 \times 10^5$) — количество элементов и количество операций.

Вторая строка содержит $n$ целых чисел $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$) — начальные элементы последовательности.

Каждая из следующих $q$ строк описывает операцию в одном из трёх форматов:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$) — операция прибавления.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$) — операция присваивания.
• 3 l r ($1 \le l \le r \le n$) — операция запроса.

Гарантируется, что на протяжении всего процесса для каждого $1 \le i \le n$ выполняется $0 \le a_i \le 10^9$.

Формат выходных данных

Для каждой операции запроса выведите в отдельной строке одно целое число — результат запроса по модулю $2^{64}$.

Примеры

стандартный ввод

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

стандартный вывод

35
39
40
34
177
120

стандартный ввод

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

стандартный вывод

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

Примечание

В первом примере:

Исходная последовательность равна 2 3 5 4 1. После третьей операции она становится равной 2 3 2 2 1, а после шестой операции — 7 8 7 7 6.

Для первого запроса ответ равен $\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$.

Для второго запроса ответ равен $\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$.