You are given N integers representing the number of doubts resolved by a Teacher Assistant(TA) in last N number of days. Rajan Bhaiya wants to analyse his performance. For that, he want the answers of k number of queries. Every query has two numbers, i and j. He wants to find the number of doubts resolved by TA from ith to jth day including both the days. Can you help him in answering these queries? Note -> Joining date of a TA will be considered his 0th day.
Input Format
First line contains 2 numbers N and K. N represents total number of days and K represents number of queries. Next line contains N space-separated integers representing the number of doubts resolved by him in N days. Next K lines contain two integers.
Output Format
K integers. (Every integer in a single row)
Constraints
1 <= N <= 10^9 1 <= k <= 10^6 0 <= doubts resolve in a single day <= 100
Example
Input
30 6 85 0 43 36 74 15 83 92 30 74 92 87 41 92 21 70 52 38 51 59 29 59 65 55 78 97 6 49 24 85 0 5 5 10 10 15 15 20 20 25 25 29
Output
253 386 403 299 383 261