Background

前缀和模板题

Description

给你一个n个元素的数组，我们想求L到R范围内的元素和

Format

Input

第一行输入一个N和M分别表示数组的大小和询问的次数（1<=N<=100000，1<=M<=100000）

第二行到第M+1行每行输入一个L和R，分别表示要求的区间的范围（1<=L<=R<=N）

Output

输出M行区间和

Samples

5 1
1 2 3 4 5
2 5

14

Limitation

1s, 1024KiB for each test case.