Nested Candy Boxes

For New Year, Andrey received a candy box. Inside it he found several identical, smaller boxes, and inside those are even smaller boxes, and so on. Formally, a candy is a box of level $0$, and a box of level $i$ contains $a_i$ boxes of level $i-1$. The box Andrey received has level $n$.

Today friends will visit Andrey, and he wants to share some candies with them. To do so, he has to open some boxes. Andrey cannot open a box that is inside a box he has not opened yet. For several values of $x$, find the minimum number of boxes Andrey must open to get at least $x$ candies. Andrey does not know yet how many friends will come, so he asks for answers to several values of $x$.

The first line contains $n$ and $m$ ($1 \le n, m \le 300\,000$), the number of boxes and the number of queries. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$). The third line contains $m$ integers $x_1, x_2, \ldots, x_m$ ($1 \le x_i \le 10^{12}$). It is guaranteed that each $x_i$ does not exceed the total number of candies in a level $n$ box.

Print $m$ integers. The $i$-th number is the minimum number of boxes Andrey must open to get at least $x_i$ candies.

In the first example, the only candy is hidden under five levels of boxes. In the second example, to get 13 candies Andrey must open the largest box, then two boxes of level 2, and finally five of the six level 1 boxes.