漫长的等待

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

曾经有一段时间,或许有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

情人节邀请赛之木姐姐的情人节梦录[Marathon]

未参加
状态
已结束
规则
OI
题目
20
开始于
2015-02-13 12:00
结束于
2015-02-15 12:00
持续时间
48.0 小时
主持人
参赛人数
273