题目描述

有一个长度为$n$的数组$a$，数组下标从$1$开始。

现在小A想要练习加减法，所以他决定奇数下标上的数字用加法，偶数位上的数字用减法。

并且他想要通过$q$次训练，每次训练计算区间$[l,r]$的结果。

即求$\sum\limits_{i=l}^{r}(-1)^{i-1}\cdot a_i=(-1)^{l-1}\cdot a_l+(-1)^{l}\cdot a_{l+1}+\cdots + (-1)^{r-1}\cdot a_r$。

输入格式

第一行两个正整数$n,q$，表示数组长度和询问次数。 第二行$n$个正整数$a_i$，表示数组中元素。 接下来$q$行，每行两个正整数$l,r$，表示询问区间。

输出格式

输出$q$行，每行一个整数表示答案。

样例 #1

样例输入 #1

10 3
8 2 3 1 2 9 7 4 8 2
1 3
2 6
9 10

样例输出 #1

9 
-7
6

提示

对于$50\%$的数据满足$1\le n,q\le 100$。 对于所有数据满足$1\le n,q\le 10^5,1\le a_i\le 100,1\le l\le r\le n$。

$a_1-a_2+a_3=9$

$-a_2+a_3-a_4+a_5-a_6=-7$

$a_9-a_{10}=6$