Problem
Chubaty le enseña a Grigory Melekhov cómo realizar un golpe de Baklan con un sable. Como objetivos, utilizan árboles n en una fila, numerados de 1 a n. Chubaty, estimó la fuerza de todos los árboles por números naturales y los anotó. Por cada árbol que Melekhov pudo cortar, recibe una cantidad de puntos igual al número escrito en el árbol, y si no puede, pierde la misma cantidad.
Chubaty le pide a Grigory que golpee los árboles del l al r, en orden ascendente de sus números. Melekhov recientemente se lastimó el hombro, por lo que puede cortar un árbol con éxito cada dos veces, es decir, si cortó un árbol con el número i, entonces no podrá cortar un árbol con el número < código>i + 1, pero podrá cortar el árbol con el número i + 2 etc.
Chubat
m una vez le pidió a Grigory que diera golpes, pero olvidó qué árboles podía talar Melekhov. Ayúdelo a determinar cuántos puntos anotó Gregory en cada intento.
Entrada
La primera línea contiene 2 números n y m (\(1 <= n, m <= 100000 \))
La segunda línea contiene números n: la fuerza de todos los árboles, donde la fuerza del árbol i se escribe en la posición i.
Las siguientes líneas m contienen pares de números l y r (\(1 < ; = l <= r <= n\)), es decir, qué parte de los árboles Chubaty pidió cortar.
Salida
Para cada consulta, imprime cuántos puntos ganó Grigory en este intento.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
6 6
1 2 3 4 5 6
16
1 5
2 6
2 5
2 4
2 2
|
-3
3
4
-2
3
2
|