A spread follows a stationary Ornstein-Uhlenbeck process, observed at regular intervals. The reversion speed, long-run mean and volatility vary between series and are not disclosed.

Every series is standardized: it has been shifted and scaled so that its observed history has mean 0 and standard deviation 1.

For each test case you receive the history of a new series and must forecast its next k values.

Training data

train.csv contains complete example series generated by the same procedure as the test series, each with its own randomly drawn characteristics. Columns: series_id, t, y — series stacked vertically, rows sorted by (series_id, t). The test series are new: their characteristics are drawn from the same distributions as the training series' but are not among them.

Input

The first line contains n and k. The second line contains the observed history x_1 ... x_n.

Output

k real numbers: your forecasts for the next k values, separated by spaces.

Scoring

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

s_j = sigma_j^2 / (sigma_j^2 + e_j^2)

the ratio of the optimal forecast's expected squared error to yours. The case score is the mean of s_1 ... s_k; the total score is the average over test cases, scaled to the problem's points.