You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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.