It was a peaceful day in the life of a student, when suddenly Timothy Li messages you about some strange anime called Date a Live. There are 
~N~ episodes in the series, and each episode 
~i~ has a rating 
~k_i~ from 1 to 10. Being super bored, you decide to give it a try. Unfortunately, you cannot live without food through the entire afternoon and the anime streamer you are using does not have a pause button for some reason. Thus, to make an intelligent decision on when to go make food, you have 
~Q~ queries in the form 
~a~ 
~b~. For each of these queries, you will simulate skipping episodes ~a~ to ~b~ (inclusive), and output the sum of the ratings of the episodes you do not skip.
Input Specification
The first line of input contains 2 integers, space separated — 
~N, Q~.
The next line contains ~N~ integers, space separated. The 
~i^{th}~ of these integers represents the rating of the ~i^{th}~ episode.
The next ~Q~ lines contain integers 
~a_i~ and 
~b_i~, the episodes that are skipped.
Output Specification
For each query, output one integer, the sum specified in the problem statement.
Constraints
~1 \le N, Q \le 500\,000~
~1 \le k_i \le 10~
~1 \le a \le b \le N~
Sample Input
10 3
5 6 7 8 3 4 5 6 1 2
1 3
2 4
1 10
Sample Output
29
26
0
Explanation of Output for Sample Input
For the first query, the first three episodes will be skipped, so the total rating is 
~8+3+4+5+6+1+2 = 29~.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
I have noticed a great correlation between the users of DMOJ and anime
This comment is hidden due to too much negative feedback. Show it anyway.
Date A Live! My favorite ever anime...
For python/all users, it may/may not be advantageous to use fast input :)
This is pretty much the only optimization you need here if you use python, not much else is needed as long as you can get the correct answer.
Thanks Weiwei!