Problem: Monocarp would like to open a bakery in his local area. But, at first, he should figure out whether he can compete with other shops.

Monocarp plans that the bakery will work for n days. On the i-th day, a_i loaves of bread will be baked in the morning before the opening. At the end of the n-th day, Monocarp will sell all the remaining bread that wasn't sold earlier with a huge discount.

Because of how bread is stored, the bakery seller sells the bread in the following order: firstly, he sells the loaves that were baked that morning; secondly, he sells the loaves that were baked the day before and weren't sold yet; then the loaves that were baked two days before and weren't sold yet, and so on. That's why some customers may buy a rather stale bread and will definitely spread negative rumors.

Let's define loaf spoilage as the difference between the day it was baked and the day it was sold. Then the unattractiveness of the bakery will be equal to the maximum spoilage among all loaves of bread baked at the bakery.

Suppose Monocarp's local area has consumer demand equal to k, it means that each day k customers will come to the bakery and each of them will ask for one loaf of bread (the loaves are sold according to the aforementioned order). If there is no bread left, then the person just doesn't buy anything. During the last day sale, all the remaining loaves will be sold (and they will still count in the calculation of the unattractiveness).

Monocarp analyzed his competitors' data and came up with m possible consumer demand values k_1, k_2, ..., k_m, and now he'd like to calculate the unattractiveness of the bakery for each value of demand. Can you help him?

Input

The first line contains two integers n and m (1 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ m ≤ 2 ⋅ 10^5) — the number of days the bakery is open and the number of possible values of consumer demand.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the number of bread loaves that will be baked each day.

The third line contains m integers k_1, k_2, ..., k_m (1 ≤ k_1 < k_2 < ... < k_m ≤ 10^9) — the possible consumer demand values in the ascending order.

Output

Print m integers: for each consumer demand, print the unattractiveness of the bakery.

Examples

Input


5 4
5 2 1 3 7
1 3 4 10


Output


4 2 1 0 


Input


8 9
3 1 4 1 5 9 2 6
1 2 3 4 5 6 7 8 9


Output


7 5 3 3 2 1 1 1 0 

Note

In the first example, let's describe what happens for couple consumer demands:

If consumer demand is equal to 1: 

  * at day 1: 5 loaves are baked and only 1 is sold with spoilage equal to 1 - 1 = 0; 
  * at day 2: 4 loaves are left and 2 more are baked. Only 1 loaf was sold and it was the loaf baked today with spoilage 2 - 2 = 0; 
  * at day 3: 4 loaves from the first day and 1 loaf from the second day left. One more loaf was baked and was sold this day with spoilage 3 - 3 = 0; 
  * at day 4: 4 loaves from the first day and 1 loaf from the second day left. 3 more loaves were baked and one of them was sold this day with spoilage 4 - 4 = 0; 
  * at day 5: 4 loaves from the first day, 1 loaf from the second day and 2 loaves from the fourth day left. 7 more loaves were baked and, since it's the last day, all 14 loaves were sold. 4 loaves from the first day have the maximum spoilage equal to 5 - 1 = 4. 

In total, the unattractiveness of the bakery will be equal to 4.

If consumer demand is equal to 10 then all baked bread will be sold in the day it was baked and will have spoilage equal to 0.

Solution (in CPP):

Solution:
//const int N = 2e5+5;
//int par[N],lo[N],hi[N];
//ll sum[N],sz[N];
//int getpar(int u){
//    if(par[par[u]] == par[u])
//        return par[u];
//    return par[u] = getpar(par[u]);
//}
//void unite(int u, int v){
//    u = getpar(u);
//    v = getpar(v);
//    assert(u != v);
//    if(u > v)
//        swap(u,v);
//    par[u] = v;
//    lo[v] = min(lo[v],lo[u]);
//    hi[v] = max(hi[v],hi[u]);
//    sum[v] += sum[u];
//    sz[v] += sz[u];
//}
//struct Event{
//    ll type;
//    ll id;
//    ll min_k;
//    ll id2;
//    bool operator<(const Event &t)const{
//        return min_k > t.min_k;
//    }
//};
//void __(){
//    _(int,n);
//    --n;
//    _(int,m);
//    _(vl,a,n);
//    ll asdf12323;
//    cin >> asdf12323;
//    _(vl,query,m);
//    priority_queue<Event> pq;
//    rep(i,n){
//        par[i] = i;
//        lo[i] = i;
//        hi[i] = i;
//        sum[i] = a[i];
//        sz[i] = 1;
//        pq.push({0,i,-a[i]+1,-1});
//    }
//    vb used(n);
//    vl ans(n+1,MOD);
//    ll largest_k = -MOD;
//    while(!pq.empty()){
//        Event e = pq.top();
//        pq.pop();
//        largest_k = max(largest_k,e.min_k);
//        if(e.type == 0){
//            if(sz[getpar(e.id)] > 1)
//                continue;
//            ans[1] = min(ans[1],largest_k);
//            int u = e.id;
//            u = getpar(u);
//            if(u == n-1)
//                continue;
//            int v = getpar(u+1);
//            assert(u != v);
//            ll tsum = sum[u]+sum[v];
//            ll tsz = sz[u]+sz[v];
//            ll min_k = (1-tsum)/tsz;
//            while(min_k*tsz+tsum <= 0)
//                ++min_k;
//            pq.push({1,u,min_k,v});
//        }
//        else{
//            int u = e.id;
//            int v = e.id2;
//            u = getpar(u);
//            v = getpar(v);
//            if(u != v){
//                unite(u,v);
//                u = getpar(u);
//                ans[sz[u]] = min(ans[sz[u]],largest_k);
//                u = getpar(u);
//                if(u == n-1)
//                    continue;
//                v = getpar(u+1);
//                assert(u != v);
//                ll tsum = sum[u]+sum[v];
//                ll tsz = sz[u]+sz[v];
//                ll min_k = (1-tsum)/tsz;
//                while(min_k*tsz+tsum <= 0)
//                    ++min_k;
//                pq.push({1,u,min_k,v});
//            }
//        }
//    }
//    ans[0] = -MOD;
//    per(i,1,n-1)
//        ans[i] = min(ans[i],ans[i+1]);
//    vl to_print;
//    for(ll &x : query)
//        x *= -1;
//    reverse(all(query));
//    int l = 0;
//    for(ll x : query){
//        while(l < n && x >= ans[l+1])
//            ++l;
//        to_print.pb(l);
//    }
//    reverse(all(to_print));
//    print to_print;
//
//
//}
//
#include <iomanip>
#include <algorithm>
#include <queue>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define REP_ZERO_INT(i,r) for(int i = 0; i < (r); ++i)
#define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT,REP_ZERO_INT)(__VA_ARGS__)
#define PER_INT(i,l,r) for(int i = (r); i >= (l); --i)
#define GET_PER_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define per(...) GET_PER_MACRO(__VA_ARGS__,PER_ANY,PER_INT,PER_ZERO_INT)(__VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<bool> vb;
const ll MOD = 1e9 + 7;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
T1 istream& read(T, T, istream& = cin);
T1 istream& operator>>(istream& stream, vector<T>& t){
    return read(all(t), stream);
}
T1 istream& read(T b, T e, istream& stream){
    for(T it = b; it != e; ++it)
        stream >> *it;
    return stream;
}
struct _print {
    string sep,end;
    bool space;
    ostream &stream;
    _print(string _sep=" ",string _end="\n",
            ostream &_stream = cout) 
        : sep(_sep),end(_end),space(false),
            stream(_stream) {}
    ~_print() { stream << end; }

    template <typename T>
        _print &operator , (const T &t) {
            if (space) stream << sep;
            space = true;
            stream << t;
            return *this;
        }
};
#define print _print(),
T1 ostream& operator<<(ostream& stream, const vector<T>& t){
    for(int i = 0; i < sz(t); ++i){
        stream << t[i];
        if(i+1 < sz(t))
            stream << ' ';
    }
    return stream;
}
#define INPUT_WITHOUT_INIT(type,name) type name; cin >> name
#define _IWI(type,name,...) type name(__VA_ARGS__); cin >> name
#define GET_INPUT_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define _(...) GET_INPUT_MACRO(__VA_ARGS__,_IWI,_IWI,_IWI,_IWI,_IWI,_IWI,INPUT_WITHOUT_INIT)(__VA_ARGS__)
const int N = 2e5+5;
int par[N],lo[N],hi[N];
ll sum[N],sz[N];
int getpar(int u){
    if(par[par[u]] == par[u])
        return par[u];
    return par[u] = getpar(par[u]);
}
void unite(int u, int v){
    u = getpar(u);
    v = getpar(v);
    assert(u != v);
    if(u > v)
        swap(u,v);
    par[u] = v;
    lo[v] = min(lo[v],lo[u]);
    hi[v] = max(hi[v],hi[u]);
    sum[v] += sum[u];
    sz[v] += sz[u];
}
struct Event{
    ll type;
    ll id;
    ll min_k;
    ll id2;
    bool operator<(const Event &t)const{
        return min_k > t.min_k;
    }
};
void __(){
    _(int,n);
    --n;
    _(int,m);
    _(vl,a,n);
    ll asdf12323;
    cin >> asdf12323;
    _(vl,query,m);
    priority_queue<Event> pq;
    rep(i,n){
        par[i] = i;
        lo[i] = i;
        hi[i] = i;
        sum[i] = a[i];
        sz[i] = 1;
        pq.push({0,i,-a[i]+1,-1});
    }
    vb used(n);
    vl ans(n+1,MOD);
    ll largest_k = -MOD;
    while(!pq.empty()){
        Event e = pq.top();
        pq.pop();
        largest_k = max(largest_k,e.min_k);
        if(e.type == 0){
            if(sz[getpar(e.id)] > 1)
                continue;
            ans[1] = min(ans[1],largest_k);
            int u = e.id;
            u = getpar(u);
            if(u == n-1)
                continue;
            int v = getpar(u+1);
            assert(u != v);
            ll tsum = sum[u]+sum[v];
            ll tsz = sz[u]+sz[v];
            ll min_k = (1-tsum)/tsz;
            while(min_k*tsz+tsum <= 0)
                ++min_k;
            pq.push({1,u,min_k,v});
        }
        else{
            int u = e.id;
            int v = e.id2;
            u = getpar(u);
            v = getpar(v);
            if(u != v){
                unite(u,v);
                u = getpar(u);
                ans[sz[u]] = min(ans[sz[u]],largest_k);
                u = getpar(u);
                if(u == n-1)
                    continue;
                v = getpar(u+1);
                assert(u != v);
                ll tsum = sum[u]+sum[v];
                ll tsz = sz[u]+sz[v];
                ll min_k = (1-tsum)/tsz;
                while(min_k*tsz+tsum <= 0)
                    ++min_k;
                pq.push({1,u,min_k,v});
            }
        }
    }
    ans[0] = -MOD;
    per(i,1,n-1)
        ans[i] = min(ans[i],ans[i+1]);
    vl to_print;
    for(ll &x : query)
        x *= -1;
    reverse(all(query));
    int l = 0;
    for(ll x : query){
        while(l < n && x >= ans[l+1])
            ++l;
        to_print.pb(l);
    }
    reverse(all(to_print));
    print to_print;


}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        __();
}