Hay 
~N~ celdas contiguas numeradas de 
~1~ a ~N~, que identifican la secuencia 
~A~.
Inicialmente, cada celda contiene los valores ![A[1] = A[2] = ..., A[N] = 0 (A[i] = 0](//dmoj.uclv.edu.cu/mathoid/4960aefb702bdea1dbe1711ddfdd9e28eb3c0698/svg)
~A[1] = A[2] = ..., A[N] = 0 (A[i] = 0~, para todo 
~1 \leq i \leq N)~: Esto significa que cada celda inicialmente es igual a 
~0~.
Un subgrupo continuo de celdas (siempre uno, dos o tres celdas) pueden ser actualizadas de la siguiente forma – Update (i, k):
- A la celda numerada
~i + 1~ se le adiciona 
~k~, si la celda existe.
- A la celda numerada
~i - 1~ se le adiciona ~k~, si la celda existe.
- A la celda
~i~ se le adiciona 
~2*k~.
Por ejemplo, si 
~N = 6~ las operaciones update [3, 6] y [4, 7] actúan de la siguiente forma:
Inicialmente: {0, 0, 0, 0, 0, 0}
Update[3, 6]: {0, 6, 12, 6, 0, 0}
Update[4, 7]: {0, 6, 19, 20, 7, 0}
Después de ejecutar algunas operaciones de actualización, podríamos estar interesados en responder preguntas de la siguiente forma:
- Un rango [u, v] es definido tal que u ≤ v.
- La respuesta a la suma de los valores de la celdas en el rango [u, v] (ambos u y v incluidos) módulo
~10^4~.
Dado ~N~ y 
~U~ consultas de actualización, usted deberá escribir un programa capaz de responder 
~Q~ preguntas.
Entrada
La primera línea contiene tres enteros: ~N~, ~U~ y 
~Q (1 \leq N, U, Q \leq 10^6)~, representando el número de celdas, el número de operaciones de actualización, y el número de consultas respectivamente. Cada una de las siguientes 
~U + Q~ líneas contienen una de dos posibles operaciones (actualización o consulta):
- Actualización: Indicado por el número ~1~, seguido por dos enteros ~i~ y ~k~
~(1 \leq i \leq N)~ y 
~(1 \leq k \leq 10^6)~ separados por un espacio, indicando la operación de actualización.
- Consulta: Indicado por el número
~2~, seguido por dos enteros 
~u~ y 
~v~ 
~(1 \leq u \leq v \leq N)~ separados por un espacio indicando la operación de consulta.
Salida
Para cada pregunta [u, v] usted deberá imprimir la suma de todas las celdas contiguas empezando en ~u~ y terminando en ~v~ módulo ~10^4~.
Ejemplo de Entrada
6 2 2
1 3 6
2 4 6
1 4 7
2 1 6
Ejemplo de Salida
6
52
Comments
C++ Te amo por tu buena optimización
Yo ese
XD