题目描述

Faster 给了你一个长为 $n$ 的数组 $a$，并问了你 $m$ 个问题。

对于每次询问，Faster 给你 $l,r,k$，问你在区间 $[l,r]$ 中（即在 $a_l,a_{l+1},...,a_{r-1},a_r$ 中）最多选多少个数满足总和不大于 $k$。如果不能满足则输出 $0$。

输入文件(faster.in)

第一行两个整数 $n,m$。

第二行有 $n$ 个整数表示数组 $a$。

以下 $m$ 行，每行给定 $l,r,k$。

输出文件(faster.out)

对于每个询问输出一行一个整数，表示最大个数。

5 5
2 3 4 1 5
1 3 8
2 5 7
1 5 6
4 4 1
2 3 1

2
2
3
1
0

5 1
-4 -3 2 1 0
1 5 -6

4

数据范围

对于 $15\%$ 的数据，$n,m\le10$；

对于 $40\%$ 的数据，$n,m\le500$；

另有 $20\%$ 的数据，$k>0$；

对于 $100\%$ 的数据，$1\le n,m\le3\times10^3,1\le l\le r\le n,|a_i|\le10^9,|k|\le10^9$​。