Problem
Chubaty enseigne à Grigory Melekhov comment effectuer une frappe Baklan avec un sabre. Comme cibles, ils utilisent n arbres d'affilée, numérotés de 1 à n. Cubaty, a estimé la force de tous les arbres par des nombres naturels et les a notés. Pour chaque arbre que Melekhov a pu couper, il reçoit un nombre de points égal au nombre écrit sur l'arbre, et s'il ne le peut pas, il perd le même montant.
Chubaty demande à Grigory de frapper les arbres de l à r, dans l'ordre croissant de leurs numéros. Melekhov s'est récemment blessé à l'épaule, il peut donc abattre un arbre avec succès une fois sur deux, c'est-à-dire que s'il abattre un arbre portant le numéro i, il ne pourra pas abattre un arbre portant le numéro < code>i + 1, mais pourra abattre l'arbre avec le numéro i + 2 etc.
Chubat
m a demandé un jour à Grigory de lui donner des coups, mais il a oublié quels arbres Melekhov pouvait abattre. Aidez-le à déterminer combien de points Gregory a marqué à chaque tentative.
Entrée
La première ligne contient 2 nombres n et m (\(1 <= n, m <= 100000 \))
La deuxième ligne contient des nombres n - la force de tous les arbres, où la force de l'arbre i est écrite à la position i.
Les lignes m suivantes contiennent des paires de nombres l et r (\(1 < ; = l <= r <= n\)), c'est-à-dire quel morceau d'arbre Cubaty a demandé d'abattre.
Sortie
Pour chaque requête, imprimez le nombre de points que Grigory a gagnés lors de cette tentative.
Exemples
| # |
Entrée |
Sortie |
| 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