#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int LG_HEIGHT = 15;
const int nmax= 5e4 + 5;
int GLOBALREZ[nmax];

struct UnionSetDriver {
   struct Node {
      Node *l, *r;
      int val;
   } *nil = new Node{0, 0, 0};
   UnionSetDriver() { nil -> l = nil -> r = nil; }
   Node mem[10'000'000]; int ptr = 0;
   
   using ns = Node*;
   struct pns {ns l, r; };
   vector<int> avail;
   void remove(ns x) {
      if(x == nil) return;
      avail.emplace_back(x - mem);
      return;
   }
   int getfirst() {
      if(sz(avail)) {
         int x = avail.back();
         avail.pop_back();
         return x;
      }
      return ptr++;
   }
   
   ns mknew(ns l, ns r, int x) { int P = getfirst(); mem[P] = Node{l, r, x}; return mem + P; }
   
   ns updnode(ns node, ns l, ns r) {
      node -> l = l;
      node -> r = r;
      if(node -> val >= 0)
         node -> val = (l -> val < 0? 1 : l -> val) + (r -> val < 0? 1 : r -> val);
      return node;
   }
   
   pns split(ns node, int val, int b = LG_HEIGHT) { // <= val in st
      if(b == -1)
         return pns{node, nil};
      pns tmp;
      int c = (val & (1 << b)) >> b;
      if(c == 0) {
         tmp = split(node -> l, val, b - 1);
         ns interm = mknew(nil, nil, 0);
         return pns{updnode(interm, tmp.l, nil), updnode(node, tmp.r, node -> r)};
      }
      else {
         tmp = split(node -> r, val, b - 1);
         ns interm = mknew(nil, nil, 0);
         return pns{updnode(interm, node -> l, tmp.l), updnode(node, nil, tmp.r)};
      }
   }
   ns merge(ns l, ns r) {
      if(l == nil) return r;
      if(r == nil) return l;
      assert(l -> val >= 0 && r -> val >= 0);
      ns x = updnode(l, merge(l -> l, r -> l), merge(l -> r, r -> r));
      remove(r);
      return x;
   }
   ns insert(ns node, int x, int b = LG_HEIGHT) {
      if(b == -1) {
         node -> val = -x;
         return node;
      }
      int c = (x & (1 << b)) >> b;
      if(c == 0) {
         node = updnode(node, insert(node -> l = (node -> l == nil? mknew(nil, nil, 0) : node -> l) , x, b - 1), node -> r);
         //cerr << x << ": " << b << '\t' << node -> val << '\n';
         return node;
      }
      if(c == 1) {
         node = updnode(node, node -> l, insert(node -> r = (node -> r == nil? mknew(nil, nil, 0) : node -> r) , x, b - 1));  
         //cerr << x << ": " << b << '\t' << node -> val << '\n';
         return node;
      }
   }
   ns getnew() { return mknew(nil, nil, 0); }
   void walkset(ns node, int setval, int b = LG_HEIGHT) {
      if(node == nil) return;
      if(b == -1) {
         GLOBALREZ[-node -> val] = setval;
         return;
      }
      walkset(node -> l, setval, b - 1);
      walkset(node -> r, setval, b - 1);
      node = updnode(node, node -> l, node -> r);
      return;
   }
};

using ns = UnionSetDriver::ns;
UnionSetDriver driver;

using Row = map<int, ns>;

int BUDGET;

struct Line {
   int m, c; int idx;
   Line(int x, int y, int z): m(x), c(y), idx(z) {;}
   void heaten(int a = 1) { c += m * a; }
   bool operator < (const Line& x) const { return c < x.c || (c == x.c && idx > x.idx); }
};

struct LowerEnvelope {
   ll sumC, sumM;
   int dim = 0;
   map<int, map<int, ns>> inside;
   
   Line react(int i, int a) {
      if(sumC > BUDGET) return Line(a, 0, i);
      return Line(a, BUDGET - sumC + a, i);
   }
   
   
   pair<Row, Row> splitworst(int remain) { // raman alea mari
      remain = worstCdim() - remain;
      map<int, ns> currents = inside.rbegin() -> second;
      int val = 0;
      for(int b = LG_HEIGHT; b >= 0; b--) {
         int L = 0, R = 0;
         for(auto [m, node] : currents) {
            L += node -> l -> val < 0? 1 : node -> l -> val;
            R += node -> r -> val < 0? 1 : node -> r -> val;
         }
         if(R <= remain) { 
            remain -= R;
            for(auto &[m, node] : currents)
               node = node -> l;
         }
         else {
            val |= (1 << b);
            for(auto &[m, node] : currents)
               node = node -> r;
         }
      }
      assert(remain == 0);
      Row L, R, o = getworst();
      ll a = 0, b = 0;
      
      for(auto [m, set] : o) {
         auto [l, r] = driver.split(set, val);
         if(l -> val > 0)
            L[m] = l;
         if(r -> val > 0)
            R[m] = r;
         a += l -> val;
         b += r -> val;
      }
      return make_pair(L, R);
   }
   Row getworst() {
      int c = inside.rbegin() -> first;
      Row r = inside[c];
      for(auto [m, set] : r) {
         dim -= set -> val;
         sumC -= c * set -> val;
         sumM -= m * set -> val;
      }
      inside.erase(c);
      return r;
   }
   void addrow(int c, map<int, ns> row) {
      for(auto [m, set] : row) {
         dim += (set -> val < 0? assert(false), 1 : set -> val);
         sumC += c * set -> val;
         sumM += m * set -> val;
         if(inside.count(c) && inside[c].count(m)) inside[c][m] = driver.merge(set, inside[c][m]);
         else inside[c][m] = set;
      }
      return;
   }
   
   void newregime() {
      sumC += sumM;
      
      map<int, map<int, ns>> tmp;
      for(auto [C, line] : inside) {
         for(auto [M, set] : line) {
            tmp[C + M][M] = set;
            //sumC += (set -> val) * (C + M);
         }
      }
      inside = tmp;
      tmp.clear();
   }
   
   int size() { return dim; }
   int worstC() { return inside.empty()? -1e9 - 5 : inside.rbegin() -> first; }
   int worstCdim() { 
      int s = 0;
      for(auto [m, set] : inside[inside.rbegin() -> first])
         s += set -> val;
      return s;
   }
   
   void insert(int c, int m, int i) {
      sumC += c;
      sumM += m;
      dim++;
      
      if(inside.count(c) && inside[c].count(m)) driver.insert(inside[c][m], i);
      else inside[c][m] = driver.getnew(), driver.insert(inside[c][m], i);
   }
   void insert(Line x) {
      insert(x.c, x.m, x.idx);
   }
};

Row makerow(Line l) {
   ns mine = driver.getnew();
   driver.insert(mine, l.idx);
   Row simple;
   simple[l.m] = mine;
   return simple;
}

struct UpperEnvelope {
   map<int, Row> inside;
   int dim = 0;
   
   Row getbest() {
      dim -= bestCdim();
      int c = inside.begin() -> first;
      Row r = inside[c];
      inside.erase(c);
      return r;
   }
   void addrow(int c, Row row) {
      for(auto [m, set] : row) {
         dim += (set -> val < 0? assert(false), 1 : set -> val);
         if(inside.count(c) && inside[c].count(m)) inside[c][m] = driver.merge(set, inside[c][m]);
         else inside[c][m] = set;
      }
      return;
   }
   
   
   void newregime() {
      map<int, map<int, ns>> tmp;
      for(auto [C, line] : inside) {
         for(auto [M, set] : line) {
            if(tmp.count(M) && tmp[M].count(M)) tmp[M][M] = driver.merge(tmp[M][M], set);
            else tmp[M][M] = set;
         }
      }
      inside = tmp;
      tmp.clear();
   }
   int size() { return dim; }
   int bestC() { return inside.empty()? 1e9 + 5 : inside.begin() -> first; }
   int bestCdim() { 
      int s = 0;
      for(auto [m, set] : inside[inside.begin() -> first])
         s += set -> val;
      return s;
   }
   void insert(int c, int m, int i) {
      if(inside.count(c) && inside[c].count(m)) driver.insert(inside[c][m], i);
      else inside[c][m] = driver.getnew(), driver.insert(inside[c][m], i);
   }
   void insert(Line x) {
      insert(x.c, x.m, x.idx);
   }
   
};

LowerEnvelope lower;
UpperEnvelope upper;

void readjust(int dim) {
   while(sz(lower) < dim || lower.worstC() >= upper.bestC()) {
      int c = upper.bestC();
      lower.addrow(c, upper.getbest());
   }
   while(sz(lower) > dim) {
      if(sz(lower) - lower.worstCdim() >= dim) {
         int c = lower.worstC();
         upper.addrow(c, lower.getworst());
      }
      else {
         int c = lower.worstC();
         auto [small, big] = lower.splitworst(sz(lower) - dim);
         lower.addrow(c, big);
         upper.addrow(c, small);
      }
   }
   return;
}


signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n >> BUDGET;
   vector<int> v(n + 1);
   for(auto &x : v | views::drop(1)) cin >> x;
   if(n == 1) {
      cout << BUDGET << '\n'; 
      exit(0);
   }
   if(n == 2) {
      cout << BUDGET << ' ' << 0 << '\n';
      exit(0);
   }
   
   {
      upper.insert(Line(rbegin(v)[1], BUDGET + rbegin(v)[1], sz(v) - 2));
      upper.insert(Line(rbegin(v)[0], rbegin(v)[0], sz(v) - 1));
   }
   
   for(int i = sz(v) - 3; i > 0; i--) {
      readjust((sz(v) - i - 1) / 2);
      auto l = lower.react(i, v[i]);
      auto simple = makerow(l);
      
      if(l.c == 0) lower.insert(l);
      else {
         lower.newregime();
         upper.newregime();
         upper.insert(l);
      }
   }
   
   for(auto [C, row] : lower.inside)
      for(auto [M, set] : row)
         driver.walkset(set, C - M);
         
   for(auto [C, row] : upper.inside)
      for(auto [M, set] : row)
         driver.walkset(set, C - M);
   
   for(int i = 1; i <= n; i++)
      cout << max(-1, GLOBALREZ[i]) << ' ';
   
   cout << '\n';
}

/**
      Binecuvanteaza Doamne Ukraina.
--
*/