Nested Candy Boxes

All submissions for this problem are available.
Andy got a box of candies for Christmas. In fact, he discovered that the box contained several identical smaller boxes, and they could contain even smaller boxes, and so on. Formally, we say that candies are boxes of level 0, and for 1 ≤ i ≤ n, a level i box contains a_{i} boxes of level i  1. The largest box has level n. Andy realized that it can take quite a long time to open all the boxes before he actually gets to eat some candies, so he put the box aside in frustration.
But today being his birthday, some friends came to visit Andy, and Andy decided to share some candies with them. In order to do that, he must open some of the boxes. Naturally, Andy can not open a box that is still inside an unopened box. If Andy wants to retrieve X candies, what is the least number of boxes he must open? You must help him answer many such queries. Each query is independent.
Input
 The first line contains two integers n and m, which refer to the level of the largest box, and the number of queries respectively.
 The second line contains n integers a_{1}, ..., a_{n}.
 The third line contains m integers X_{1}, ..., X_{m}.
Output
 Print m integers each in a new line, i^{th} of them equal to the smallest number of boxes Andy must open in order to retrieve at least X_{i} candies.
Constraints
 1 ≤ n,m ≤ 300000
 1 ≤ a_{i} ≤ 10^{9}
 1 ≤ X_{i} ≤ 10^{12}
 It is guaranteed that the total number of candies is at least X_{i} for all i
Example
Input 1: 5 1 1 1 1 1 1 1 Output 1: 5 Input 2: 3 3 3 3 3 2 8 13 Output 2: 3 5 8
Explanation
Testcase 1: The only candy is contained in five levels of boxes.
Testcase 2: In the third query, for 13 candies, Andy should open the largest box, two level2 boxes, and finally five of six available level1 boxes. Each of those boxes will contain 3 level0 boxes (which are candies). So he'll have 15 candies in total, but he needs only 13 of them.
Author:  admin2 
Tags  admin2 
Date Added:  22122017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 