K-variance#11317

K-variance

1 second

128 megabytes

Very easy

Consider the variance of the sequence $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n as

\frac{\sum _{i = 1}^{n} ( a _{i} - a ˉ ) ^{2}}{n - 1}

\sqrt{\sum_{i=1}^n (a_i - \bar{a})^2 \over n - 1}

where

a ˉ = \frac{\sum _{i = 1}^{n} a _{i}}{n}

\bar{a} = {\sum_{i=1}^n a_i \over n}

Consider the K-variance as the variance of the consecutive subsequence of length $k$ .

Your task is to calculate all $(n - k + 1)$ (n - k + 1) K-variances for the given sequence and $k$ .

Formally, the $i$ -th $(1 \leq i \leq n - k + 1)$ (1 \le i \le n - k + 1) K-variance $r_{i}$ r_i is the variance of sequence ${a_{i}, a_{i + 1}, ..., a_{i + k - 1}}$ \{a_i, a_{i+1}, ..., a_{i+k-1}\}.

Input

The first line contains two integers $n$ and $k (2 \leq k \leq n \leq 1 0^{5})$ k~(2 \le k \le n \le 10^5).

The second line contains $n$ integers $a_{1}, a_{2}, ..., a_{n} (∣ a_{i} ∣ \leq 100)$ a_1, a_2, ..., a_n~(|a_i| \le 100).

Output

Print $(n - k + 1)$ (n - k + 1) lines with real numbers $r_{1}, r_{2}, ..., r_{n - k + 1}$ r_1, r_2, ..., r_{n-k+1}.

The answer is considered correct if its absolute or relative error does not exceed $1 0^{- 4}$ 10^{-4}.

Examples

Example 1

Loading

Example 2

Loading

a_{1}, a_{2}, ..., a_{n}

\frac{\sum _{i = 1}^{n} ( a _{i} - a ˉ ) ^{2}}{n - 1}

a ˉ = \frac{\sum _{i = 1}^{n} a _{i}}{n}

(n - k + 1)

(1 \leq i \leq n - k + 1)

r_{i}

{a_{i}, a_{i + 1}, ..., a_{i + k - 1}}

k (2 \leq k \leq n \leq 1 0^{5})

a_{1}, a_{2}, ..., a_{n} (∣ a_{i} ∣ \leq 100)

(n - k + 1)

r_{1}, r_{2}, ..., r_{n - k + 1}

1 0^{- 4}