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

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

Условие

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

  1. Среднеквадратичное отклонение (СКО) всей полученной последовательности не должно отклоняться от СКО исходных данных более чем на 103
  2. Абсолютная разница между прогнозами за два соседних дня на спрогнозированном участке и при переходе от исходных данных к нему не должна превышать утроенную среднюю абсолютную разницу на исходном участке (|aj − aj1| ≤ 3 M, 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.036s 0.007s 15