Balama

La examenul de prelucrare a lemnului, inginerii-în-devenire au primit o ușă cu $N$ balamale, fiecare cu o rezistență $R_1, \dots , R_N$.

Prima probă din examen constă în determinarea rezistenței totale a ușii, care este un șir $T_1, \dots , T_K$ format din $K$ numere, calculat după cum urmează.

Prima data, se definește matricea $A_{ij}$ cu $N - K + 1$ linii și $K$ coloane, astfel încât a $i$-a linie a lui $A$ este subsecvența $R_i , \dots , R_{i+K-1}$ a șirului $R$. De exemplu, dacă $N = 9$, $R = [2, 5, 4, 3, 2, 1, 8, 7, 3]$ și $K = 3$, atunci:

Apoi, se definește matricea $B_{ij}$, tot cu $N - K + 1$ linii și $K$ coloane, astfel încât a $i$-a a lui $B$ conține exact elementele liniei $i$ din matricea $A$, dar în ordine crescătoare. De exemplu, pentru valorile precedente ale lui $N$ și $R$ avem că:

În final, definim $T_j$ ca fiind maximul coloanei $j$ din $B$, adică $T_j = \max_i B_{ij}$. În exemplul de mai sus, maximele coloanelor sunt $3$, $7$, $8$, și sunt încadrate în dreptunghiuri.

Cerință

Dându-se $N$, $K$ și $R_1, \dots , R_N$, să se calculeze $T_1, \dots , T_K$.

Date de intrare

Prima linie din fișierul balama.in va conține numerele $N$ și $K$, cu semnificația din enunț. Pe următoarea linie se vor afla rezistențele celor $N$ balamale $R_1, \dots, R_N$, separate prin spații.

Date de ieșire

În fișierul de ieșire balama.out se vor afișa $K$ numere separate prin spații, al $i$-lea număr reprezentând $T_i$.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $1 \leq K \leq N$
• $0 \leq R_i \leq 10^9$ pentru $1 ≤ i ≤ N$

Notă: Subtaskul 5 conține cinci grupe de teste, în valoare de $7$, $8$, $8$, $9$ și respectiv $10$ puncte.

Exemplu

balama.in

9 3
2 5 4 3 2 1 8 7 3

balama.out

3 7 8

Explicație

Matricea $A$ are valorile

$\begin{pmatrix} 2 & 5 & 4\\ 5 & 4 & 3\\ 4 & 3 & 2\\ 3 & 2 & 1\\ 2 & 1 & 8\\ 1 & 8 & 7\\ 8 & 7 & 3 \end{pmatrix}$

Matricea $B$ are valorile

$\begin{pmatrix} 2 & 4 & 5\\ 3 & 4 & 5\\ 2 & 3 & 4\\ 1 & 2 & 3\\ 1 & 2 & 8\\ 1 & 7 & 8\\ 3 & 7 & 8 \end{pmatrix}$

Maximele coloanelor sunt $3$, $7$, $8$.