漫长的等待
描述
曾经有一段时间，或许有5年，甚至更长吧。我与木姑娘失去了联系，怎么也联系不上。
那一段日子真的很艰难，我却总是能想起她。
细细数来，从我一声不吭离开，到再次见到她，过去了n天。每天都会不止一次想起她的身影。其中第i天会想起来她ai次。
再次相遇的时候，我向她坦白这一点。她不信。
她给我提出了m个问题，每次都是问我“从第l天到第r天中，有几天你想了我至少k次，却不超过w次？”
格式
输入格式
第一行2个整数n和m(1<=n<=100000,1<=m<=1000000)
之后一行给出n个数a1,a2,...,an
之后m行每行给出4个整数，依次为l,r,k,w
输出格式
输出m行对应m次询问的答案
样例1
样例输入1
10 5
1 2 3 4 1 2 5 3 2 4
1 4 1 3
1 4 1 4
1 4 2 10
1 10 1 2
1 10 1 3
样例输出1
3
4
3
5
7
限制
30％的数据，n<=3000，m<=3000。
50％的数据，n<=50000，m<=100000。
100%的数据，n<=100000，m<=1000000。
1<=ai<=1000000000
