Hay una secuencia $A_0, A_1, \ldots, A_{n-1}$ de longitud $n$. Escribe un programa que ejecute las siguientes consultas:

• 1 l r c: Suma $c$ a todos los $A_i$ en el intervalo $l \le i \le r$.
• 2 l r d: Reemplaza todos los $A_i$ en el intervalo $l \le i \le r$ por $\lfloor A_i/d \rfloor$.
• 3 l r: Imprime el mínimo de todos los $A_i$ en el intervalo $l \le i \le r$.
• 4 l r: Imprime la suma de todos los $A_i$ en el intervalo $l \le i \le r$.

donde $\lfloor x \rfloor$ denota el mayor entero $y$ tal que $y \le x$ (por ejemplo, $\lfloor -2.5 \rfloor = -3$, $\lfloor -7 \rfloor = -7$).

Entrada

La primera línea contiene dos enteros $n$ y $q$ ($1 \le n, q \le 100{,}000$), que indican la longitud de la secuencia y el número de consultas.

La segunda línea contiene $n$ enteros $A_0, A_1, \ldots, A_{n-1}$ ($-10^9 \le A_i \le 10^9$).

Cada una de las siguientes $q$ líneas contiene una consulta ($0 \le l \le r \le n-1$, $-10^4 \le c \le 10^4$, $2 \le d \le 10^9$).

Salida

Cada vez que se encuentre una consulta de tipo 3 o tipo 4, imprime una respuesta por línea.

Ejemplos

Entrada 1

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9

Salida 1

-2
-2
-2
-2
0
1
1