Después de la selección del equipo provincial, White cayó en un largo período de decepción. No lograba encontrar ninguna esperanza en sus resultados. Aun así, White continuó con su entrenamiento final antes de la NOI. Además de su entrenamiento habitual, también comenzó a explorar temas que nunca había tenido la oportunidad de aprender durante sus días en la OI — esperando que, antes de decir adiós, no quedaran más remordimientos.

Sacudiéndose sus pensamientos errantes, White de repente se concentró en un problema frente a ella, un problema de estructuras de datos simple y aburrido —

White tiene una secuencia de $n$ enteros $a_1, a_2, \dots, a_n$. Realizará $q$ operaciones sobre esta secuencia. Cada operación es de uno de los siguientes tres tipos:

• 1 l r v — Sumar $v$ a cada elemento en el intervalo $[l, r]$.
• 2 l r v — Asignar el valor $v$ a cada elemento en el intervalo $[l, r]$.
• 3 l r — Consultar el valor de $\sum_{i=l}^r (\min_{j=l}^i a_j) \times (\max_{j=l}^i a_j)$ módulo $2^{64}$.

Tu tarea es simular todas las operaciones y mostrar los resultados de todas las consultas.

Entrada

La primera línea de la entrada contiene dos enteros $n, q$ ($1 \le n, q \le 2 \times 10^5$), que representan el número de elementos y el número de operaciones.

La segunda línea contiene $n$ enteros $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 10^9$), que representan los elementos iniciales.

Cada una de las siguientes $q$ líneas describe una operación, en uno de los tres formatos:

• 1 l r v ($1 \le l \le r \le n, -10^9 \le v \le 10^9$), que representa la operación de suma.
• 2 l r v ($1 \le l \le r \le n, 1 \le v \le 10^9$), que representa la operación de asignación.
• 3 l r ($1 \le l \le r \le n$), que representa la operación de consulta.

Se garantiza que $0 \le a_i \le 10^9$ para cada $1 \le i \le n$ durante todo el proceso.

Salida

Para cada operación de consulta, imprime un entero en una sola línea — el resultado de la consulta módulo $2^{64}$.

Ejemplos

Entrada

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

Salida

35
39
40
34
177
120

Entrada

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

Salida

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

Nota

En el primer caso de prueba:

La secuencia original es 2 3 5 4 1. Después de la tercera operación, se convierte en 2 3 2 2 1, y después de la sexta operación, se convierte en 7 8 7 7 6.

Para la primera consulta, la respuesta es $\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$.

Para la segunda consulta, la respuesta es $\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$.