Problem
Chubaty insegna a Grigory Melekhov come eseguire un colpo Baklan con una sciabola. Come bersagli, usano n alberi in fila, numerati da 1 a n. Chubaty, ha stimato la forza di tutti gli alberi in base a numeri naturali e li ha annotati. Per ogni albero che Melekhov è riuscito a tagliare, riceve un numero di punti pari al numero scritto sull'albero e, se non ci riesce, perde lo stesso importo.
Chubaty chiede a Grigory di colpire gli alberi da l a r, in ordine crescente di numero. Melekhov si è recentemente fatto male alla spalla, quindi può abbattere con successo un albero ogni due volte, ad es. se abbatte un albero con il numero i, non sarà in grado di abbattere un albero con il numero i, quindi non sarà in grado di abbattere un albero con il numero < code>i + 1, ma sarà in grado di abbattere l'albero con il numero i + 2 ecc.
Chubat
m una volta chiese a Grigory di eseguire colpi, ma dimenticò quali alberi Melekhov poteva abbattere. Aiutalo a determinare quanti punti ha segnato Gregory per ogni tentativo.
Input
La prima riga contiene 2 numeri n e m (\(1 <= n, m <= 100000 \))
La seconda riga contiene n numeri - la forza di tutti gli alberi, dove la forza dell'albero i è scritta nella posizione i.
Le seguenti righe m contengono coppie di numeri l e r (\(1 < ; = l <= r <= n\)), indicando quale pezzo di alberi Chubaty ha chiesto di abbattere.
Uscita
Per ogni query stampa quanti punti ha guadagnato Grigory in questo tentativo.
Esempi
| # |
Input |
Uscita |
| 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
|