Problem: You've got a non-decreasing sequence x1, x2, ..., xn (1 ≤ x1 ≤ x2 ≤ ... ≤ xn ≤ q). You've also got two integers a and b (a ≤ b; a·(n - 1) < q).

Your task is to transform sequence x1, x2, ..., xn into some sequence y1, y2, ..., yn (1 ≤ yi ≤ q; a ≤ yi + 1 - yi ≤ b). The transformation price is the following sum: <image>. Your task is to choose such sequence y that minimizes the described transformation price.

Input

The first line contains four integers n, q, a, b (2 ≤ n ≤ 6000; 1 ≤ q, a, b ≤ 109; a·(n - 1) < q; a ≤ b).

The second line contains a non-decreasing integer sequence x1, x2, ..., xn (1 ≤ x1 ≤ x2 ≤ ... ≤ xn ≤ q).

Output

In the first line print n real numbers — the sought sequence y1, y2, ..., yn (1 ≤ yi ≤ q; a ≤ yi + 1 - yi ≤ b). In the second line print the minimum transformation price, that is, <image>.

If there are multiple optimal answers you can print any of them.

The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.

Examples

Input

3 6 2 2
1 4 6


Output

1.666667 3.666667 5.666667 
0.666667


Input

10 100000 8714 9344
3378 14705 17588 22672 32405 34309 37446 51327 81228 94982


Output

1.000000 8715.000000 17429.000000 26143.000000 34857.000000 43571.000000 52285.000000 61629.000000 70973.000000 80317.000000 
797708674.000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const int mod = 1000000007;
const int gmod = 3;
const int inf = 1039074182;
const double eps = 1e-9;
const double pi = 3.141592653589793238462643383279;
const long long llinf = 2LL * inf * inf;
template <typename T1, typename T2>
inline void chmin(T1 &x, T2 b) {
  if (b < x) x = b;
}
template <typename T1, typename T2>
inline void chmax(T1 &x, T2 b) {
  if (b > x) x = b;
}
inline void chadd(int &x, int b) {
  x += b - mod;
  x += (x >> 31 & mod);
}
template <typename T1, typename T2>
inline void chadd(T1 &x, T2 b) {
  x += b;
  if (x >= mod) x -= mod;
}
template <typename T1, typename T2>
inline void chmul(T1 &x, T2 b) {
  x = 1LL * x * b % mod;
}
template <typename T1, typename T2>
inline void chmod(T1 &x, T2 b) {
  x %= b, x += b;
  if (x >= b) x -= b;
}
template <typename T>
inline T mabs(T x) {
  return (x < 0 ? -x : x);
}
using namespace std;
using namespace std;
template <typename T>
ostream &operator<<(ostream &cout, const vector<T> &vec) {
  cout << "{";
  for (int i = 0; i < (int)vec.size(); i++) {
    cout << vec[i];
    if (i != (int)vec.size() - 1) cout << ',';
  }
  cout << "}";
  return cout;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &cout, pair<T1, T2> p) {
  cout << "(" << p.first << ',' << p.second << ")";
  return cout;
}
template <typename T, typename T2>
ostream &operator<<(ostream &cout, set<T, T2> s) {
  vector<T> t;
  for (auto x : s) t.push_back(x);
  cout << t;
  return cout;
}
template <typename T, typename T2>
ostream &operator<<(ostream &cout, multiset<T, T2> s) {
  vector<T> t;
  for (auto x : s) t.push_back(x);
  cout << t;
  return cout;
}
template <typename T>
ostream &operator<<(ostream &cout, queue<T> q) {
  vector<T> t;
  while (q.size()) {
    t.push_back(q.front());
    q.pop();
  }
  cout << t;
  return cout;
}
template <typename T1, typename T2, typename T3>
ostream &operator<<(ostream &cout, map<T1, T2, T3> m) {
  for (auto &x : m) {
    cout << "Key: " << x.first << ' ' << "Value: " << x.second << endl;
  }
  return cout;
}
template <typename T1, typename T2>
void operator+=(pair<T1, T2> &x, const pair<T1, T2> y) {
  x.first += y.first;
  x.second += y.second;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2> &x, const pair<T1, T2> &y) {
  return make_pair(x.first + y.first, x.second + y.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2> &x, const pair<T1, T2> &y) {
  return make_pair(x.first - y.first, x.second - y.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(pair<T1, T2> x) {
  return make_pair(-x.first, -x.second);
}
template <typename T>
vector<vector<T>> operator~(vector<vector<T>> vec) {
  vector<vector<T>> v;
  int n = vec.size(), m = vec[0].size();
  v.resize(m);
  for (int i = 0; i < m; i++) {
    v[i].resize(n);
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      v[i][j] = vec[j][i];
    }
  }
  return v;
}
void print0x(int x) {
  std::vector<int> vec;
  while (x) {
    vec.push_back(x & 1);
    x >>= 1;
  }
  std::reverse(vec.begin(), vec.end());
  for (int i = 0; i < (int)vec.size(); i++) {
    std::cout << vec[i];
  }
  std::cout << ' ';
}
template <typename T>
void print0x(T x, int len) {
  std::vector<int> vec;
  while (x) {
    std::cout << (x & 1);
    x >>= 1;
    len--;
  }
  while (len--) cout << 0;
}
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while (!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
  }
  return res;
}
void debug_out(vector<string> __attribute__((unused)) args,
               __attribute__((unused)) int idx,
               __attribute__((unused)) int LINE_NUM) {
  cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
  if (idx > 0)
    cerr << ", ";
  else
    cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss;
  ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
using namespace std;
int n, q, a, b;
int x[6005];
long double ans[6005];
struct F {
  long double a, b, c;
  long double minPlace(const long double &l, const long double &r) const {
    if ((r - l) <= eps) return l;
    if (a == 0 && b == 0) return l;
    if (a == 0) return (b > 0 ? l : r);
    if (a > 0) {
      long double t = -b / a / 2;
      if (t < l) t = l;
      if (t > r) t = r;
      return t;
    } else {
      long double t = -b / a / 2;
      return mabs(t - l) > mabs(t - r) ? l : r;
    }
  }
  long double operator()(const long double &pos) const {
    return a * pos * pos + b * pos + c;
  }
  F shift(long double xs) const {
    return F({a, -2 * a * xs + b, xs * xs * a - b * xs + c});
  }
};
F f[12005];
long double w[12005];
int len;
char tr[12005][12005];
int sz[12005];
long double xm[12005];
int main() {
  cin >> n >> q >> a >> b;
  for (int i = 0; i < n; i++) scanf("%d", x + i);
  f[len++] = F({0, 0, 0});
  w[0] = 1;
  w[1] = q;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < len; j++) {
      f[j].a++;
      f[j].b -= (x[i] << 1);
      f[j].c += 1LL * x[i] * x[i];
    }
    if (i == n - 1) break;
    pair<long double, int> o = make_pair(INFINITY, 0);
    for (int j = 0; j < len; j++) {
      long double p = f[j].minPlace(w[j], w[j + 1]);
      chmin(o, make_pair(f[j](p), j));
    }
    int pos = o.second;
    long double xm = f[pos].minPlace(w[pos], w[pos + 1]);
    for (int j = len + 1; j > pos + 1; j--) {
      f[j] = f[j - 2].shift(b - a);
      tr[i][j] = -2;
      w[j + 1] = w[j - 1] + (b - a);
    }
    w[pos + 1] = xm;
    w[pos + 2] = xm + (b - a);
    f[pos + 1] = F({0, 0, f[pos](xm)});
    tr[i][pos + 1] = -1;
    len += 2;
    for (int j = 0; j <= len; j++) w[j] += a;
    for (int j = 0; j < len; j++) f[j] = f[j].shift(a);
    sz[i] = len;
    ::xm[i] = xm;
    while (w[len - 1] > q) len--;
  }
  pair<long double, pair<long double, int>> res =
      make_pair(INFINITY, make_pair(0.0, 0));
  for (int i = 0; i < len; i++) {
    if (w[i] > q) break;
    chmin(res, make_pair(
                   f[i](f[i].minPlace(w[i], min(w[i + 1], (long double)q))),
                   make_pair(f[i].minPlace(w[i], min(w[i + 1], (long double)q)),
                             i)));
  }
  int pos = res.second.second;
  ans[n - 1] = res.second.first;
  for (int i = n - 2; i >= 0; i--) {
    if (tr[i][pos] == -2) {
      pos -= 2;
      ans[i] = ans[i + 1] - b;
    } else if (tr[i][pos] == -1) {
      pos -= 1;
      ans[i] = xm[i];
    } else {
      ans[i] = ans[i + 1] - a;
    }
  }
  for (int i = 0; i < n; i++) {
    printf("%.10Lf ", ans[i]);
  }
  cout << endl;
  cout.precision(10);
  cout << fixed;
  cout << res.first << endl;
  return 0;
}