Se da una secuencia $A_0, A_1, \ldots, A_{N-1}$ de longitud $N$. Escribe un programa que procese las siguientes consultas ($0 \le A_i < 2^{32}$):

• 1 p v: Insertar $v$ antes de $A_p$. Si $p$ es igual a la longitud de $A$, se inserta al final. ($0 \le p \le$ longitud de $A$, $0 \le v < 2^{32}$)
• 2 p: Eliminar $A_p$. ($0 \le p <$ longitud de $A$)
• 3 p v: Cambiar $A_p$ a $v$. ($0 \le p <$ longitud de $A$, $0 \le v < 2^{32}$)
• 4 l r k: Calcular $(\sum A_i \times (i - l + 1)^k) \bmod 2^{32}$ y mostrar el resultado. ($0 \le k \le 10$)

Entrada

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

La segunda línea contiene $A_0, A_1, \ldots, A_{N-1}$.

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.

Salida

Para cada consulta, imprime la respuesta en una línea separada.

Ejemplos

Entrada 1

4
1 2 3 5
7
4 0 2 0
1 3 4
4 2 4 1
2 0
4 0 3 1
3 1 2
4 0 1 0

Salida 1

6
26
40
4