1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll LL_INF = 10000000000000+44;


struct Ho {
  ll start;
  ll end;
  ll grow;
  ll collapse_time;
  ll accurate_at_time;
  Ho* prev;
  Ho* next;
};

struct Greater {
  bool operator()(const pair<ll, Ho*>& lhs, const pair<ll, Ho*>& rhs) const { // should rhs go first
    if (lhs.first == rhs.first) {
      if (!lhs.second && !rhs.second)
        return false;
      if (!lhs.second && rhs.second) {
        return false;
      }
      if (lhs.second && !rhs.second) {
        return true;
      }
      return rhs.second->start < lhs.second->start;
    }
    return lhs.first > rhs.first;
  }
};

int main() {
  ios_base::sync_with_stdio(0);
  
  int N, M;
  cin >> N >> M;
  
  priority_queue<pair<ll, Ho*>, vector<pair<ll, Ho*>>, Greater> events;
  
  vector<ll> P(N), Psorted(N);
  for (int i = 0; i < N; ++i) {
    cin >> P[i];
    Psorted[i] = P[i];
  }
    
  vector<ll> Q(M);
  for (int i = 0; i < M; ++i) {
    cin >> Q[i];
    events.push({Q[i], nullptr});
  }
  unordered_map<ll, ll> Ans;
  
  Ho dummy;
  Ho* first = new Ho{0, LL_INF, 0, LL_INF, 0, &dummy, nullptr};
  dummy.next = first;
  Ho* last = first;
  
  ll current_grow = 0;
  ll ct = 0;
  ll ans = 0;
  
  sort(Psorted.begin(), Psorted.end());
  for (ll t : Psorted) {
    if (t == last->start) {
      ++last->grow;
      current_grow += last->grow;
    } else {
      last->end = t;
      last->collapse_time = ct + (last->end - last->start + last->grow) / (1+last->grow);
      last->next = new Ho{t, LL_INF, 0, LL_INF, 0, last, nullptr};
      last = last->next;
    }
  }
  
  for (Ho* ho = first; ho != nullptr; ho = ho->next) {
    events.push({ho->collapse_time, ho});
  }
  
  while (!events.empty()) {
    auto q = events.top();
    ll next = q.first;
    Ho* ho = q.second;
    events.pop();
    //if (next == ct) continue;
    
    ans += current_grow * (next - ct);
    ct = next;
    
    //cerr << "ct = " << ct << " (cg=" << current_grow << ") ans =" << ans << ",  ho = " << ho << endl;
    
    if (ho && ho->start < ho->end) {
      
      //for (Ho* ho = starting; ho != nullptr; ho = ho->next)
      {
        
        if (ho->end == LL_INF) break;
        //cerr << " ho <" << ho->start << ":" << ho->end << "> g " << ho->grow << "  ct=" << ho->collapse_time << endl;
        
        if (ho->collapse_time == ct) {
          //cerr << "collapse!" << endl;     
          
          ll carry = 0;
          ll incgrow = 0;
          Ho* cho;
          for(cho = ho; cho != nullptr; cho = cho->next) {    
            //cerr << "  cho <" << cho->start << ":" << cho->end << "> g " << cho->grow << "  ct=" << cho->collapse_time << endl;
            
            assert(cho->collapse_time >= ct);
        
        
            ans += carry * (cho->grow+1);
            //cerr << "  carried " << carry << " mul " << (cho->grow+1) << endl;
                
            cho->start += carry;
            cho->start += cho->grow * (ct - cho->accurate_at_time);
            cho->end -= (ct - cho->accurate_at_time);
            cho->accurate_at_time = ct;
            
            //cerr << "   set to <" << cho->start << ":" << cho->end << "> g " << cho->grow << "  ct=" << cho->collapse_time << endl;
            
            
            if (cho->start >= cho->end) {
              carry = cho->start - cho->end;
              incgrow += cho->grow + 1; 
              
              //cerr << "   rg: " << cho->grow << " " << ( (cho->grow)*(cho->grow+1)/2) << endl;
              
              current_grow -= (cho->grow)*(cho->grow+1)/2;       
            } else {
              
              
              //cerr << "   dg: " << cho->grow << " " << ( (cho->grow)*(cho->grow+1)/2) << endl;
              current_grow -= (cho->grow)*(cho->grow+1)/2;  
              cho->grow += incgrow;            
              current_grow += (cho->grow)*(cho->grow+1)/2;              
              //cerr << "   ag: " << cho->grow << " " << ( (cho->grow)*(cho->grow+1)/2) << endl;
              
              cho->collapse_time = ct + (cho->end - cho->start + cho->grow) / (1+cho->grow);
              events.push({cho->collapse_time, cho});
              break;
            }
          }
          
          assert(ho->start >= ho->end);
          ho->prev->next = cho;
          if (cho)
            cho->prev = ho->prev;
          //ho->next = cho;
        }
      }    
    }
    
    Ans[ct] = ans;
    //cerr << "ct = " << ct << "  final ans =" << ans << endl;
  }
  
  for (auto q : Q) {
    cout << Ans[q] << endl;
  }
  
  return 0;
}