B'LuoTianyi gives you an array a of n integers and the index begins from 1 . Define g(i,j) as follows: There are q queries. For each query you are given four integers l,r,x,y , you need to calculate sum limits_{i=l}^{r} sum limits_{j=x}^{y}g(i,j) . The first line contains two integers n and q ( 1 <= n,q <= 10^6 ) -- the length of the array a and the number of queries. The second line contains n integers a_1,a_2, ldots,a_n ( 1 <= a_i <= n ) -- the elements of the array a . Next q lines describe a query. The i -th line contains four integers l,r,x,y ( 1 <= l <= r <= n, 1 <= x <= y <= n ) -- the integers in the i -th query. Print q lines where i -th line contains one integer -- the answer for the i -th query. In the first example: In the first query, the answer is g(1,4)+g(1,5)=3+3=6 . x=1,2,3 can satisfies {a_p:1 <= p <= 4 } subseteq {a_q:x <= q <= 4 } , 3 is the largest integer so g(1,4)=3 . In the second query, the answer is g(2,3)+g(3,3)=3+3=6 . In the third query, the answer is 0 , because all i > j and g(i,j)=0 . In the fourth query, the answer is g(6,6)=6 . In the second example: In the second query, the answer is g(2,3)=2 . In the fourth query, the answer is g(1,4)+g(1,5)=2+2=4 . '...