Після відбору до команди провінції 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$.