You observe n consecutive values of a time series built from random shocks. Shocks are rare, and they cluster: a shock makes further shocks more likely for a while. Shock sizes are heavy-tailed and mostly positive. A shock of size s at time tau adds to every later value y_t the amount

s * (1 - exp(-u / r)) * (A * exp(-u / d) + P), u = t - tau

a response that rises over a few steps and then decays, leaving a permanent shift. On top of that, independent noise is added at every time step. The parameters r, d, A, P, the arrival process of the shocks, the distribution of their sizes and the noise level are not disclosed and vary between test cases; the shock times and sizes are hidden.

Forecast the next h values of the series.

Input

The first line contains n and h. Each of the next n lines contains one value of the series, in time order, with 6 digits after the decimal point.

Output

h real numbers: your forecasts of the next h values, in order.

Scoring

Forecast k steps ahead is scored by its predictive efficiency

s_k = sigma_k^2 / (sigma_k^2 + e_k^2)

where e_k is the distance between your forecast and the conditional expectation of the value k steps ahead given the true state of the process at the end of the series, and sigma_k is the standard deviation of that value around its conditional expectation. The case score is the mean of s_1 ... s_h, and the total score is the mean over the cases.

Constraints

n = 1500

h = 20