Shopping

题号：NC210535
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Danny is going shopping to buy some toys. There are $n$ shops in his town which lies on a line. The $i$ th shop has exactly one toy in it and costs $a_i$ yuan. Danny wants to know the maximum number of toys he can buy if he has $z$ yuan and only buys toys from $x$ th shop to $y$ th shop.

输入描述:

The first line contains two integers $n,m (1<=n<=100000,1<=m<=100000)$ , the number of shops and number of queries.

Next line contains $n$ integers $a_i (1<=a_i<=100000)$ , the cost of toy in each shop.

Next $m$ lines, each line contains three integers $x,y,z (1<=x<=y<=n,0<=z<=10^{12})$ .

输出描述:

For each query, output an integer, the maximum number of toys Danny can buy.

示例1

输入

复制

5 5
10 7 6 9 13
1 2 11
3 4 16
1 5 8
2 4 15
1 5 100000

输出

复制