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
#include<iostream>

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)

using namespace std;

const int MAX_N = 50000, MAX_H = 64;

unsigned short W[1+MAX_H], V[1+MAX_N], S[1+MAX_N];

int A[1+MAX_N], Q[1+MAX_N];

int n, m, k, g, t, ix, mix;

int main(void) {	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	FOR(i, 1, n) cin >> A[i];
	
	FOR(i, 1, n) S[i] = 0;
	Q[n] = m + A[n];
	
	FORD(p, n-1, 1) {

		FOR(w, 0, 64) W[w] = 0;

		mix = p+1;
		FOR(i, p+1, n) {
			if (Q[i] <= MAX_H) {
				V[i] = W[Q[i]];
				W[Q[i]] = i;
			} else {
				if (Q[i] <= Q[mix]) mix = i;
			}
		}		
		
		k = (n-p) / 2;
		g = m;
		t = 0;
		while (k > 0) {
			while(t <= MAX_H && !W[t]) t++;
			if (t <= MAX_H) {
				ix = W[t];
				W[t] = V[ix];
				S[ix] = 1;
				g -= t;
				if (g < 0) break;
				k--;
			} else {
				S[mix] = 1;
				g -= Q[mix];
				break;
			}
		}
		if (g < 0) {
			Q[p] = 0;
			FOR(i, p+1, n) S[i] = 0;
			continue;
		}
		Q[p] = g + A[p];
		S[p] = 0;		

		FOR(i, p+1, n) {
			if (S[i]) {
				Q[i] += A[i];
				S[i] = 0;
			} else {
				Q[i] = A[i];
			}
		}
	}
	FOR(i, 1, n) Q[i] = (Q[i] == 0) ? -1: Q[i]-A[i];
	
	FOR(i, 1, n-1) cout << Q[i] << " "; cout << Q[n] << endl;
	
	return 0;
}