Hugo is a Year 69 student at the prestigious Patrick Mouratoglou Tennis Academy, home to future tennis legends and borderline superhumans. Determined to improve his game and one day win a Grand Slam, Hugo trains relentlessly — rain or shine, weekday or weekend. Every day, he logs the exact number of minutes he spends practicing, down to the last serve and sprint drill.

His coach, Bobby, is known for his data-driven approach. “Tennis is math in motion,” Bobby often says. Lately, Bobby has been peppering Hugo with questions like:

• “How much did you practice during Week 4 of Block B?”
• “Did your training volume drop before the clay season?”

Hugo, exhausted from practice, doesn’t want to manually sum up training logs every time. So he turns to you — the academy’s resident programming wizard.

You're given Hugo’s log of training durations, and a list of Bobby’s questions. Each question asks for the total number of minutes Hugo trained between two specific days.

Can you answer Bobby’s queries efficiently, before he makes Hugo calculate them on a whiteboard again?

Input

N Q

A₁ A₂ A₃ ... A_n

L₁ R₁

L₂ R₂

...

L_Q R_Q

1 ≤ N, Q ≤ 10⁵

1 ≤ A[i] ≤ 10⁴

1 ≤ L_i ≤ R_i ≤ N

Output

For each query, output a single number: the total number of minutes Hugo trained from day L_i to day R_i

Example

Input:
5 3
10 20 30 40 50
1 3
2 4
1 5

Output:
60
90
150