|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #35Ended |
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