You've got a non-decreasing sequence *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*n*</sub> (1 ≤ *x*<sub class="lower-index">1</sub> ≤ *x*<sub class="lower-index">2</sub> ≤ ... ≤ *x*<sub class="lower-index">*n*</sub> ≤ *q*). You've also got two integers *a* and *b* (*a* ≤ *b*; *a*·(*n* - 1) &lt; *q*).

Your task is to transform sequence *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*n*</sub> into some sequence *y*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">2</sub>, ..., *y*<sub class="lower-index">*n*</sub> (1 ≤ *y*<sub class="lower-index">*i*</sub> ≤ *q*; *a* ≤ *y*<sub class="lower-index">*i* + 1</sub> - *y*<sub class="lower-index">*i*</sub> ≤ *b*). The transformation price is the following sum: <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/2932f339c0d0f43caa55ecad28d2426256d02ff5.png" style="max-width: 100.0%;max-height: 100.0%;"/>. Your task is to choose such sequence *y* that minimizes the described transformation price.
The first line contains four integers *n*, *q*, *a*, *b* (2 ≤ *n* ≤ 6000; 1 ≤ *q*, *a*, *b* ≤ 10<sup class="upper-index">9</sup>; *a*·(*n* - 1) &lt; *q*; *a* ≤ *b*).

The second line contains a non-decreasing integer sequence *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*n*</sub> (1 ≤ *x*<sub class="lower-index">1</sub> ≤ *x*<sub class="lower-index">2</sub> ≤ ... ≤ *x*<sub class="lower-index">*n*</sub> ≤ *q*).
(* It's a DP algorithm.  Keep y_opt.(i) which is the natural place
   where the point y.(i) will land when considering only points 0, 1,
   2... i.
   
   To compute y_opt.(i) we assume we have already computed the
   previous ones.  What we do now is see if y.(i) acting alone would
   be within the window defined by y_opt.(i-1).  If it is, we're done
   with y_opt.(i).  Say y.(i) is too high to be compatible with
   y_opt.(i-1).  Then we glue these two points together by asserting
   y.(i)-y.(i-1)=b.  (Analogously, if y.(i) is too low compared to
   y_opt.(i-1) we assert y.(i)-y.(i-1)=a instead.)  This pair of
   points has a natural position uninfluenced by anything outside of
   them.  If this position is compatible with y_opt.(i-2) then we're
   done, otherwise we add y.(i-2) to the chain and continue.  So the
   elements are chained together by a sequence of as and bs,
   intermixed.

   We can prove by induction that the solution that this finds is
   optimal.  The base case is when y.(i) is within the window allowed
   by y_opt.(i-1).  Clearly this is the right answer.  Now suppose
   that we have established that in the optimal solution some chain of
   differences relating y.(k),...,y.(i-2), y.(i) must occur.  This
   means that when searching for the optimal solution we need only
   consider these values moving in lockstep as specified by the chain.
   Looking at point k-1 if the chain is too low, then the optimal
   solution must also have y.(k-1) in the chain being a below y.(k),
   and if point k-1 is too high then it must be in the chain b below
   y.(i).  (The intuition is that of a spring.  If you move your
   finger toward a spring and you touch the spring, pushing harder on
   the spring will keep your finger in contact with the spring.  The
   spring will not suddenly pull away from your finger as you push
   harder.  The (x-y)^2 cost function ensures that this is the correct
   model.)

   So the algorithm is O(n^2).  It might be possible to work out a
   version of this algorithm that is O(n log n) by keeping the chains
   in a search tree.  Then instead of starting from scratch each time
   when adding a new point, it would edit the current chain.  It is
   not clear that this can be made to work.

               Danny Sleator <[email protected]>
*)

let read_int _ = Scanf.bscanf Scanf.Scanning.stdib " %d " (fun x -> x)
let read_float _ = Scanf.bscanf Scanf.Scanning.stdib " %f " (fun x -> x)

let rec fold i j f init = if i>j then init else fold (i+1) j f (f i init)
let sum i j f = fold i j (fun i a -> (f i) +. a) 0.0
let sq x = x *. x
let (++) (a,b,c) (d,e,f) = (a+.d, b+.e, c+.f)

let quad_min (a,b,c) = -. (b /. (2.0 *. a))
  (* ax^2 + bx + c is our quadratic.  Return the value of x that minimizes it *)
  (* a cannot be zero *)

let () =
  let n = read_int 0 in
  let q0 = read_float 0 in
  let a0 = read_float 0 in
  let b0 = read_float 0 in

  let x = Array.init n read_float in
  let y_opt = Array.copy x in
  let chain = Array.make n 0.0 in

  let bound h v = max (1.0+.h) (min q0 v) in

  let rec pull_chain j h q = if j<0 then (bound h (quad_min q), j) else
    (* Set the group of points j+1, j+2, ... i all to differ by cumulative h
       the quadratic represented by this group is q. *)
    let yi_nat = bound h (quad_min q) in
      if y_opt.(j) < yi_nat -. h -. b0 then 
	let ny = x.(j) +. h +. b0 in
	  chain.(j) <- b0;
	  pull_chain (j-1) (h+.b0) (q ++ (1.0, -2.0 *. ny, sq ny))
      else if y_opt.(j) > yi_nat -. h -. a0 then 
	let ny = x.(j) +. h +. a0 in
	  chain.(j) <- a0;
	  pull_chain (j-1) (h+.a0) (q ++ (1.0, -2.0 *. ny, sq ny))
      else 
	(yi_nat, j)
  in

    for i=1 to n-1 do
      let myq = (1.0, -2.0*.x.(i), sq x.(i)) in
      let (yopt, j) = pull_chain (i-1) 0.0 myq in
	y_opt.(i) <- yopt;
    done;

    let rec fill_in_y i = if i<0 then () else
      let (_, j) = pull_chain (i-1) 0.0 (1.0, -2.0*.x.(i), sq x.(i)) in
	for k=i-1 downto j+1 do
	  y_opt.(k) <- y_opt.(k+1) -. chain.(k);
	done;
	fill_in_y j
    in
      fill_in_y (n-1);
      
      let total = sum 0 (n-1) (fun i-> sq (y_opt.(i) -. x.(i))) in

	for i=0 to n-1 do 
	  Printf.printf "%.8f " y_opt.(i);
	done;
	Printf.printf "%.8f\n" total;
