史莱克学院近期对外开放N天，第i天(1 \leq i \leq N)有A_i人来访。

请编写一个程序来回答以下共Q个问题：

• 第1个问题：第L_1天到第R_1天的总来访人数是多少？

• 第2个问题：第L_2天到第R_2天的总来访人数是多少？

• \vdots

• 第Q个问题：第L_Q天到第R_Q天的总来访人数是多少？

输入第一行包含两个整数N和Q，分别表示开放的天数和问题的数量。

第二行包含N个整数A_1, A_2, \ldots, A_N，其中A_i表示第i天的来访人数。

接下来的Q行，每行包含两个整数L_i和R_i，表示第i个问题询问的日期范围。

总共输出Q行。在第i行(1 \leq i \leq Q)中，请输出第i个问题的答案，以整数形式。

提示

样例1说明

这个输入包含5个问题。

• 第1个问题询问第2天到第3天的总来访人数，答案是6+9=15。

• 第2个问题询问第1天到第4天的总来访人数，答案是8+6+9+1=24。

数据范围

• 1 \leq N,Q \leq 10^5

• 1 \leq A_i \leq 10000

• 1 \leq L_i \leq R_i \leq N