El Sr. Verum trabaja en OI Pharmaceutical Co., Ltd. En esta empresa, los investigadores están ocupados con experimentos trabajar para desarrollar nuevos aerosoles de esterilización.

En esta empresa, la fuerza de un spray de esterilización se define de la siguiente manera: cuando usamos un spray de fuerza ~x~ una vez para una placa de cultivo con ~y~ bacterias, el número de bacterias en ella se convierte en \(⌊y / x⌋\), que es el número entero obtenido de ~y / x~ redondeando por debajo. Ahora, se desarrolla un nuevo spray de fuerza ~K~. Para probar el rendimiento de este spray, planean experimentar con él. Usan placas de cultivo ~N~ numeradas ~1,. . . , N~. Al principio, hay ~C_i~ bacterias en la placa de cultivo ~i~. En el experimento, implementan operaciones ~Q~ en esta secuencia. Cada operación es una de los siguientes:

• Operación 1: elija una placa de cultivo ~a~ y un número entero ~b~, y ajuste el número de bacterias en la placa de cultivo ~a~. Después de esta operación, el número de bacterias en la placa de cultivo ~a~ se convierte en ~b~.

• Operación 2: Elija dos números enteros ~l, r~ con ~1 \le l \le r \le N~. esterilizar (convertir las cantidad de bacterias de una placa de cultivo con ~x~ bacterias en \(⌊\frac{x}{K}⌋\)) una vez para cada una de las placas de cultivo ~l, l + 1,. . . , r - 1, r~.

• Operación 3: Elija dos números enteros ~l, r~ con ~1 \le l \le r \le N~. Calcule la suma del número de bacterias en las placas de cultivo ~l, l + 1,. . . , r - 1, r~, y regístrelo.

El Sr. Verum siente curiosidad por los resultados del experimento, asumiendo que el nuevo aerosol funciona como se esperaba. Como un buen programador, te pide que predigas los resultados del experimento. Escribe un programa que determine los números registrados por la operación 3 en el experimento.

Tarea

Dada la fuerza del aerosol y la información sobre las operaciones en el experimento, escriba un programa que determina los números registrados por la operación 3s.

Entrada

Lea los siguientes datos de la entrada estándar.

• La primera línea de entrada contiene tres números enteros separados por espacios ~N, Q, K~. Esto significa la fuerza del aerosol es ~K~, el número de placas de cultivo es ~N~ y el número de operaciones en el experimento es ~Q~.

• La ~i~-ésima línea ~(1 \le i \le N)~ de las siguientes ~N~ líneas contiene un entero ~C_i~. Esto significa que hay ~C_i~ bacterias en la placa de cultivo ~i~ al comienzo del experimento.

• La ~i~-ésima línea ~(1 \le i \le Q)~ de las siguientes líneas ~Q~ contiene tres enteros separados por espacios ~S_i, T_i, U_i~. Ellos indican información sobre la i-ésima operación en el experimento.

  • Cuando ~S_i = 1~, se refieren a la operación ~1~ con ~a = T_i, b = U_i~.

  • Cuando ~S_i = 2~, se refieren a la operación ~2~ con ~l = T_i, r = U_i~.

  • Cuando ~S_i = 3~, se refieren a la operación ~3~ con ~l = T_i, r = U_i~.

Salida

Escribe los números registrados por la operación 3 en el experimento. El número de líneas en la salida es igual al número de operaciones 3 implementadas en el experimento.

Restricciones

Todos los datos de entrada cumplen las siguientes condiciones.

• ~1 \le N \le 100 000~.

• ~1 \le Q \le 100 000~.

• ~1 \le K \le 10~.

• ~0 \le C_i \le 1 000 000 000 (1 \le i \le N)~.

• ~1 \le S_i \le 3 (1 \le i \le Q)~.

• Cuando se satisface ~S_i = 1, 1 \le T_i \le N~ y ~0 \le U_i \le 1 000 000 000 (1 \le i \le Q)~.

• Cuando ~S_i = 2, 3~ se satisface, ~1 \le T_i \le U_i \le N (1 \le i \le Q)~.

Puntuación

Se garantiza que en casos por un valor del 10% del total:

• ~1 \le N \le 3000~.

• ~1 \le Q \le 3000~.

Se garantiza que en casos por un valor del 10% del total:

• ~K = 1~.

Se garantiza que en casos por un valor del 20% del total:

• ~C_i \le 1 (1 \le i \le N)~.

• Cuando se satisface ~S_i = 1, U_i \le 1 (1 \le i \le Q)~.

Entradas y salidas de muestra

Entrada de muestra 1

5 10 3
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5

Salida de muestra 1

8
3
8

• Al comienzo del experimento, el número de bacterias en las placas de cultivo es 1 2 8 1 3.

• Ajuste el número de bacterias en la placa de cultivo de 2 a 5. Después de esta operación, el número de bacterias en las placas de cultivo son 1 5 8 1 3.

• El número de bacterias en las placas de cultivo 3, 4, 5 se divide por 3 y se redondea en fracciones. Después de este operación, el número de bacterias en las placas de cultivo es 1 5 2 0 1.

• Dado que la suma del número de bacterias en las placas de cultivo 2, 3, 4, 5 es 8, escriba 8 en el resultado.

• El número de bacterias en las placas de cultivo 1, 2, 3, 4 se divide por 3 y se redondea en fracciones. Después de este operación, el número de bacterias en las placas de cultivo es 0 1 0 0 1.

• Ajuste el número de bacterias en la placa de cultivo de 3 a 2. Después de esta operación, el número de bacterias en las placas de cultivo son 0 1 2 0 1.

• Dado que la suma del número de bacterias en las placas de cultivo 3, 4, 5 es 3, escriba 3 en el resultado.

• Ajuste el número de bacterias en la placa de cultivo de 2 a 4. Después de esta operación, el número de bacterias en las placas de cultivo son 0 4 2 0 1.

• El número de bacterias en las placas de cultivo 1, 2, 3, 4 se divide por 3 y se redondea en fracciones. Después de este operación, el número de bacterias en las placas de cultivo es 0 1 0 0 1.

• Ajuste el número de bacterias en la placa de cultivo de 3 a 2. Después de esta operación, el número de bacterias en las placas de cultivo son 0 1 2 0 1.

• Dado que la suma del número de bacterias en las placas de cultivo 3, 4, 5 es 3, escriba 3 en el resultado.

• Ajuste el número de bacterias en la placa de cultivo de 2 a 4. Después de esta operación, el número de bacterias en las placas de cultivo son 0 4 2 0 1.

• El número de bacterias en las placas de cultivo 1, 2 se divide por 3 y se redondea en fracciones. Después de este operación, el número de bacterias en las placas de cultivo es 0 1 2 0 1.

• Ajuste el número de bacterias en la placa de cultivo de 1 a 4. Después de esta operación, el número de bacterias en las placas de cultivo son 4 1 2 0 1.

• Dado que la suma del número de bacterias en las placas de cultivo 1, 2, 3, 4, 5 es 8, escriba 8 en el resultado.

Entrada de muestra 2

15 10 3
25
87
32
89
24
99
57
88
10
57
65
42
66
98
13
3 9 12
1 7 15
3 2 9
2 1 14
3 10 13
1 10 6
2 14 14
1 7 96
3 14 15
3 10 12

Salida de muestra 2

174
444
76
23
41