You observe n consecutive values of a stationary AR(p) process

x_t = c + phi_1 x_{t-1} + ... + phi_p x_{t-p} + eps_t

with iid Gaussian innovations. The order p (at most 8), the coefficients, the intercept and the innovation variance are not disclosed and vary between test cases. Values are given with 6 digits after the decimal point.

Forecast the next h values of the process.

Input

The first line contains n and h. Each of the next n lines contains one value x_1 ... x_n in time order.

Output

h real numbers: your forecasts of x_{n+1} ... x_{n+h}.

Scoring

Under the true process, the expected squared error of your forecast of x_{n+k} equals sigma_k^2 + e_k^2, where sigma_k is the standard deviation of the optimal k-step forecast error and e_k is the distance between your forecast and the conditional expectation of x_{n+k} given x_1 ... x_n. Forecast k is scored by its predictive efficiency

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

the ratio of the optimal forecast's expected squared error to yours. The case score is the mean of s_1 ... s_h.

Constraints

n = 2000

h = 10