joey-goes-to-the-army

After getting fed up of his acting career,joey has finally decided to join the army.Now being a procrastinator,he fails to qualify the test.So,the commander of the army asks him to do some maths for other soldiers.

The army system is unique in a way that all soldiers are divided into a pair of cadet and officer. There are a total of n ranks among cadets and officers. The order in which all soldiers stand are as per their ranks as well as their post(only if rank is same). For example, a cadet/officer with rank 2 will always stand before cadet/officer with rank 3. Similarly,a cadet of rank 3 will always stand before officer of rank 3.

All soldiers are standing in a row as per the above conditions with mines in between. There are a total of n mines in a row and soldiers ,taking  risk are standing on the  mines.Each mine has a risk factor equal to mine[i]. A mine is moderately dangerous for a pair of cadet and officer of the same rank if the risk factor of that mine is greater than some value k1 and less than some value k2 for each pair.

Now,joey’s task is to inform each cadet-officer pair, given their danger value , the sum of danger value of all the mines between them that are not dangerous.

Input
First line will contain 2 integers N and K denoting total mines in a row and total number of cadet-officer pairs respectively.
Second line will contain N integers mine[i] determining the danger value of each mine.
Next k lines will contain 4 integers k1 k2 li ri where k1 and k2 are the lower bound and upper bound for a mine to be moderately dangerous and li ri are the ranks of cadet and officer respectively.

Output
Output k lines each containing the sum of moderately dangerous mines.

Input Constraints
1 ≤ N ≤ 10^5
1 ≤ k ≤ 10^5
1 ≤ mine[i] ≤ 10^9
1 ≤ k1 ≤ k2 ≤ 10^9
1 ≤ li ≤ ri ≤ N
l1 ≤ l1 ≤ .... ≤ ln
r1 ≤ r2 ≤ ... ≤ rn

SAMPLE INPUT
5 2
1 2 3 4 5
2 3 1 3
2 2 1 5

SAMPLE OUTPUT
5
2

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: