Max Food Per Request

You are given an array A of length n, where A[i] represents the number of food items in the i-th storage unit. There are m requests. Each request is represented by three integers l, r, k. For each request, you need to calculate the sum of the food items from storage units l to r (1-indexed) and then output the minimum between this sum and k. In other words, for each request, if ( S = \sum_{i=l}^{r} A[i] ), the answer is ( \min(S, k) ).

Input Format:
The first line contains two integers n and m. The second line contains n integers representing the array A. The following m lines each contain three integers l, r, and k describing a request.

Output Format:
For each request, output one line with the answer, which is the maximum number of food items that can be taken from the specified range. The answer for each query is the minimum of the total food items available in the range and the number k given in the request.

inputFormat

The input is read from standard input (stdin). The first line contains two integers n (the number of storage units) and m (the number of requests). The second line contains n space-separated integers, the elements of array A. Then m lines follow, each containing three space-separated integers l, r, k, representing a request.

outputFormat

For each of the m requests, output a single integer on a new line, which is the answer for that request. The answer is the minimum between the total sum of food items in the range [l, r] and k.## sample

6 3
5 20 15 10 7 25
1 3 40
2 5 30
1 6 50

40
30
50