I. Broken sword
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Daniyar is a brave knight who fights against $$$n$$$ monsters arranged in a row. The $$$i$$$-th monster from the left has a strength of $$$a_i$$$.

Daniyar has a sword of length $$$k$$$, which allows him to kill no more than $$$k$$$ consecutive monsters with one swing. After he kills the monsters, the remaining monsters move forward, closing the row again.

However, Daniyar can swing his sword no more than $$$m$$$ times before getting tired and unable to continue the fight.

Daniyar's main goal is to defeat the strongest monsters before he gets too tired to continue the battle. Therefore, he wants to minimize the strength of the strongest monster that will still be alive after this battle.

Unfortunately, just before the battle, Daniyar broke his sword. To solve this problem, he urgently needs to go to the nearest blacksmith to buy a new sword. However, he is not sure about the length of the sword he should buy. He wants to determine the minimum strength of the strongest monster that would still be alive if he had a sword of length $$$k$$$ for each possible value of $$$k$$$ ($$$1 \le k \le n$$$).

Input

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 3 \cdot 10^5)$$$ — the number of monsters and the number of times Daniyar can swing his sword, respectively.

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the strength of each monster.

Output

For each $$$k$$$ ($$$1 \le k \le n$$$), output the minimum possible strength of the strongest monster that will still be alive after the battle if Daniyar had a sword of length $$$k$$$, or $$$0$$$ if he can kill all the monsters.

Examples
Input
5 1
3 5 4 1 2
Output
4 3 2 2 0
Input
3 2
3 1 2
Output
1 0 0