C - Carrying pumpkins

Time limit: 5 s
Memory limit: 512 MiB
Languages: C, C++, Java, Python, ... (details)

Fito is collecting some pumpkins that are lying on a line.

For each pumpkin, he knows his weight. Believe it or not, small pumpkins can be heavier than bigger ones. He has a truck that he will use as transportation but it cannot carry more than a given weight in total. Moreover, he can only collect a consecutive interval of pumpkins because otherwise, he might destroy some of the remaining ones.

Given some queries with the maximum weight the truck can carry, your task is to help Fito finding out how many ways he has for choosing the pumpkins he will pick up.

Input

The first line of the input contains two numbers $N$ ($1\leq N \leq 10^5$) and $Q$ ($1 \leq Q\leq 500$). The second line contains $N$ integers $w_i$ separated by a space ($1 \leq w_i \leq 10^9$)  that represent the weights of the pumpkins in the same order they are lying on the line. The third line contains $Q$ integers $q_i$ ($1 \leq q_i \leq 10^{14}$) separated by a space which are the queries. 

Output

For each query $q_i$, print in one line the number of ways Fito has for choosing the pumpkins if the truck can carry a total maximum weight of $q_i$.

Sample test(s)

Input
3 4 1 2 3 1 3 5 6
Output
1 4 5 6
Input
6 5 5 10 8 8 8 1 27 1 30 18 3
Output
16 1 16 12 1