You observe a noisy cyclical signal. The signal oscillates persistently, but its cycle is irregular: the phase is not locked, the cycle duration drifts slowly and randomly over time, and occasionally it changes abruptly. The typical cycle length, the drift magnitude, the jump behavior and the noise level 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 h 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 T and h (500 <= T <= 2000, 10 <= h <= 100). The second line contains the observed history y_1 ... y_T.

Output

Output h real numbers: your forecasts for y_{T+1} ... y_{T+h}.

Scoring

Let m_j and sigma_j be the mean and standard deviation of y_{T+j} conditional on the true state of the signal at time T (its phase and current cycle length, which you do not observe). Forecast j is scored by its predictive efficiency

s_j = sigma_j^2 / (sigma_j^2 + (f_j - m_j)^2)

where f_j is your forecast: the ratio of the expected squared error of a forecaster who knew the true state to yours. The case score is the mean of s_1 ... s_h; the total score is the average over test cases, scaled to the problem's points.