Casey and April

Limits: 7 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Casey Jones has an array \(a\) of \(n\) elements. Today he doesn’t like this array that much, so he decided to transform it.

April prepared an interesting median transformation for Casey. The result of the median transformation of array \(a\) is an array \(b\) of size \(n\) such that \(b_i = median(a_{i-1}, a_i, a_{i+1})\), where \(median(x, y, z)\) is the middle value after sorting the numbers \(x\), \(y\), and \(z\) in ascending order. For convenience, we assume that \(a_0=a_n\) and \(a_{n+1}=a_1\).

Now Casey is wondering what the array will look like if the median transformation is applied to it \(k\) times.

Input

The first line contains two integers \(n\) and \(k\).

The second line contains \(n\) integers \(a_i\).

Output

Output \(n\) integers – the array after \(k\) transformations.

Constraints

\(3 \le n \le 4 \cdot 10^5\),

\(1 \le k \le 10^9\),

\(1 \le a_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 2 4 7 47 14 17 11 9	7 7 14 14 14 11 9

Notes

First transformation:

• \(b_1 = median(9, 4, 7) = 7\);

• \(b_2 = median(4, 7, 47) = 7\);

• \(b_3 = median(7, 47, 14) = 14\);

• \(b_4 = median(47, 14, 17) = 17\);

• \(b_5 = median(14, 17, 11) = 14\);

• \(b_6 = median(17, 11, 9) = 11\);

• \(b_7 = median(11, 9, 4) = 9\).

So after the first transformation, the array is equal to [7, 7, 14, 17, 14, 11, 9].

After the second transformation, the array becomes equal to [7, 7, 14, 14, 14, 11, 9].