Задача A. Краткосрочный прогноз

Автор:И. Олейников   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Вася работает брокером. Его главная задача — предугадывать котировки акций различных компаний, чтобы знать, какие акции надо покупать, а какие продавать. Вася располагает записями котировок акций некоторой компании за предыдущие N дней, и ему нужен прогноз развития ситуации на рынке на следующие K дней. Запись котировок представляет собой последовательность действительных чисел ai, 1 ≤ i ≤ N. Прогноз должен представлять собой продолжение этой последовательности aj, N + 1 ≤ j ≤ N + K. На прогноз накладываются следующие условия

  1. Среднеквадратичное отклонение (СКО) всей полученной последовательности не должно отклоняться от СКО исходных данных более чем на 10 − 3
  2. Абсолютная разница между прогнозами за два соседних дня на спрогнозированном участке и при переходе от исходных данных к нему не должна превышать утроенную среднюю абсолютную разницу на исходном участке (|aj − aj − 1| ≤ 3M, N + 1 ≤ j ≤ N + K)
Поскольку Вася хочет прогнозировать как можно точнее, он решил использовать компьютерную программу, которая помогала бы ему в этом. Написать эту программу он заказал вам.

Формат входного файла

Входной файл содержит два числа N и K, за которыми следует N вещественных чисел — котировки акций.

Формат выходного файла

Выходной файл должен содержать K вещественных чисел — прогноз ситуации на рынке.

Исходные данные таковы, что хотя бы одно решение всегда существует.

Если решений несколько, вывести любое из них.

Ограничения

2 ≤ N ≤ 4000, 1 ≤ K ≤ N,  − 109 ≤ ai ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1
5.01
5.0
5.0
5.0
5

0.068s 0.011s 13