For Turbo C++ Users : Read the following document before attempting the question :

Problem description.

HM has a tree-cutting facility. He also paint logs to sell them for treehouse-making. His assistant Deepsaggas is a student of IIIT-Delhi. He loves competitive programming very much. He has been working hard and practicing so much that nothing seemed to challenge him anymore. Uncle John called him up to paint the fences. Deepsaggas in turn, called up his friend KB to help him. Now KB was a lazy guy. He just started from any random log at position 'L' and kept painting the logs till some log at position 'R'. Now painting a log costs money. And due to the unfinished work, Deepsaggas want to find the cost to paint the remaining logs ( Before the 'L' log and After the 'R' log). Help him in the same.

Input
First line contains integers N and Q,denoting the number of logs in the fence and number of queries respectively. Second line of each test case contains N space separated integers, where i^th integer denotes the cost to paint the i^th log.
Next Q line contain two space-separated integers L,R on each line

Note that each query is independent of each other

Output
For each test case, print the cost of painting the remaining logs.

The output for each test case should be separated by a new line (See Sample cases for more information).

Constraints

Example
Input:
5 3
1 2 3 4 5
2 3
4 4
4 5

Output:
10
11
6

见题面

见题面