중첩된 사탕 상자

안드레이는 새해 선물로 사탕 상자를 받았다. 상자를 열어 보니 같은 모양의 더 작은 상자가 여러 개 들어 있었고, 그 안에는 또 더 작은 상자가 들어 있었다. 형식적으로 사탕은 레벨 $0$인 상자로 본다. 레벨 $i$인 상자에는 레벨 $i-1$인 상자가 $a_i$개 들어 있다. 안드레이가 받은 상자의 레벨은 $n$이다.

오늘 친구들이 찾아오면 안드레이는 사탕을 나눠 주려고 한다. 이를 위해 상자를 여러 개 열어야 한다. 안드레이는 아직 열지 않은 상자 안에 든 상자를 열 수 없다. 여러 $x$ 값에 대해, 사탕을 최소 $x$개 얻기 위해 열어야 하는 상자 개수의 최솟값을 구하라. 친구가 몇 명 올지 아직 정하지 못해서 안드레이는 여러 $x$ 값에 대한 답을 알고 싶어 한다.

첫 줄에 상자 개수 $n$과 질문 개수 $m$이 주어진다 ($1 \le n, m \le 300\,000$). 둘째 줄에는 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^9$). 셋째 줄에는 정수 $x_1, x_2, \ldots, x_m$이 주어진다 ($1 \le x_i \le 10^{12}$). 각 $x_i$는 레벨 $n$인 상자에 들어 있는 사탕의 총 개수를 넘지 않는다.

$m$개의 정수를 출력한다. $i$번째 수는 사탕을 $x_i$개 이상 얻기 위해 안드레이가 열어야 하는 상자 개수의 최솟값이다.

첫 번째 예시에서 사탕은 다섯 단계의 상자 안에 숨어 있다. 두 번째 예시에서 사탕 13개를 얻으려면 가장 큰 상자를 연 다음, 레벨 2 상자 두 개를 열고, 마지막으로 레벨 1 상자 여섯 개 중 다섯 개를 연다.