Задача D. Автокорреляция

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть задан временной ряд Yn1 = {yt}nt = 1. Требуется написать программу, вычисляющую значения коэффициентов автокорреляции Пирсона rl = corr(Yn − l1, Ynl), l = 1,m.

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

Первая строка входных данных содержит целые числа n и m — длину ряда и максимальное значение задержки. Вторая строка входного файла содержит n вещественных чисел — временной ряд.

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

Выходной файл должен содержать m вещественных чисел — значения коэффициента автокорреляции с точностью не менее трёх знаков после запятой.

Ограничения

2 ⩽ m < n ⩽ 103

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 2
1 1 2 2 1 1 2 2 1 1
0.1 -1

0.047s 0.008s 13