Se tiene una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$. Escribe un programa que procese las siguientes consultas:

• 1 L R X: Para cada $i$ tal que $L \le i \le R$, asigna $A_i = A_i + X$.
• 2 L R: Para cada $i$ tal que $L \le i \le R$, asigna $A_i = \lfloor \sqrt{A_i} \rfloor$.
• 3 L R: Imprime $A_L + A_{L+1} + \ldots + A_R$.

Entrada

La primera línea contiene el tamaño de la secuencia $N$. ($1 \le N \le 100{,}000$)

La segunda línea contiene $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 100{,}000$)

La tercera línea contiene el número de consultas $M$. ($1 \le M \le 100{,}000$)

Las siguientes $M$ líneas contienen cada una una consulta. ($1 \le L \le R \le N$, $1 \le X \le 100{,}000$) Al menos aparece una consulta de tipo 3.

Salida

Imprime los resultados de cada consulta de tipo 3 en orden, uno por línea.

Ejemplos

Entrada 1

5
1 2 3 4 5
5
1 3 5 2
2 1 4
3 2 4
2 3 5
3 1 5

Salida 1

5
6