Maximum Subarray Sum with Length Constraint

You are given an array of integers and a list of queries. For each query, you need to find the maximum sum of any contiguous subarray whose length is at most k (given in the query). The subarray must be contiguous and can have a length between 1 and k.

Formally, for an array \(a_1, a_2, \ldots, a_n\) and a positive integer \(k\), find \[ \max_{1 \leq i \leq n}\;\max_{1 \leq \ell \leq k \text{ and } i+\ell-1 \leq n} \;\sum_{j=i}^{i+\ell-1} a_j. \]

You need to answer multiple queries on the same array.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains two integers \(n\) and \(q\), where \(n\) is the number of elements in the array and \(q\) is the number of queries.
2. The second line contains \(n\) space-separated integers, representing the elements of the array.
3. The third line contains \(q\) space-separated integers, where each integer \(k\) denotes the maximum allowed length for the subarray in that query.

outputFormat

Print \(q\) integers on a single line separated by spaces. Each integer is the maximum subarray sum for the corresponding query.

5 3
1 -2 3 4 -5
1 2 5

4 7 7