Guri and Prary are good friends and are chocolate lovers. They win a lottery and get a chance to visit ChocoLand for few minutes.

In ChocoLand, there are N number of chocolate containers kept one next to other, one unit apart. Each of the container contains Ki number of chocolates. Guri and Prary should pack as many chocolates as possible in the given time which they could take away to their home. To maximise number of chocolates they could pack, they start at different positions G1, P1(possibly equal) and start moving on only one side. Depending on their individual speeds, both of them cover different units and reach the positions G2, P2 collecting all the chocolates on their way.

After coming out of ChocoLand, on their way back to home, they are eager to know number of chocolates that they collected. But are finding it difficult. So given the situation, help Guri and Prary by finding the total number of chocolates they collected. They do not exactly remember the position they started from or where they end. So they give Q number of queries. Where each query includes starting and ending positions of Guri and Prary and you have to calculate the chocolates they could collect in all these cases

Input:
First line contains two integers N Q where N = number of containers in ChocoLand, Q = number of queries.
Second line contains N numbers denoting number of chocolates in each container in order.
Q cases follows. Each query includes two lines.
First line has G1, P1. Starting positions of Guri and Prary.
Second line has G2, P2. Ending positions of Guri and Prary.
Note: ChocoLand is very near to ByteLand, so even they follow zero-based numbering for positions.

Output:
Print total number of chocolates they could collect in total.

Constraints:
1 ≤ Q ≤ 10^5
1 ≤ N ≤ 10^6
1 ≤ Ki ≤ 10^6
0 ≤ G1 ≤ G2 < N
0 ≤ P1 ≤ P2 < N

Large I/O files. Use scanf() and printf() instead of cin and cout

Problem Setter : Vinay Kumar

SAMPLE INPUT
7 2
1 2 1 1 3 1 1
1 4
2 6
0 2
3 5

SAMPLE OUTPUT
8
9

Explanation

For first query G1 = 1, G2 = 2, P1 = 4, P2 = 6.
So the duo collects all the chocolates from these positions. i.e. (2+1) + (3+1+1) = 8

见题面

见题面