题目描述

在木材加工考试中，未来的工程师们得到了一扇有 $N$ 个铰链的门。第 $i$ 个铰链的强度为 $R_i$。

考试的第一项任务是确定这扇门的“总强度”。总强度是一个由 $K$ 个数组成的序列

$$T_1,T_2,\ldots,T_K,$$

计算方式如下。

首先定义矩阵 $A$。矩阵 $A$ 有 $N-K+1$ 行、$K$ 列，第 $i$ 行是序列 $R$ 中从 $R_i$ 到 $R_{i+K-1}$ 的连续子序列。也就是说：

$$A_{i,j}=R_{i+j-1}\qquad (1\le i\le N-K+1,\ 1\le j\le K).$$

例如，当

$$N=9,\quad R=[2,5,4,3,2,1,8,7,3],\quad K=3$$

时，矩阵 $A$ 为：

$$A= \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}.$$

接着定义矩阵 $B$。矩阵 $B$ 同样有 $N-K+1$ 行、$K$ 列，第 $i$ 行由矩阵 $A$ 第 $i$ 行的元素按升序排列得到。

对上面的例子，有：

$$B= \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}.$$

最后，定义 $T_j$ 为矩阵 $B$ 第 $j$ 列的最大值：

$$T_j=\max_i B_{i,j}.$$

在上例中，各列最大值分别为 $3,7,8$。

任务

给定 $N,K$ 以及 $R_1,R_2,\ldots,R_N$，求出 $T_1,T_2,\ldots,T_K$。

输入格式

第一行包含两个整数 $N,K$。

第二行包含 $N$ 个整数 $R_1,R_2,\ldots,R_N$，表示每个铰链的强度。

输出格式

输出 $K$ 个整数，用空格分隔。第 $i$ 个整数表示 $T_i$。

数据范围与子任务

• $1\le N\le 200000$；
• $1\le K\le N$；
• $0\le R_i\le 10^9$，对所有 $1\le i\le N$。

子任务	分值	限制
1	5	$1\le N\le 1000$
2	6	$1\le N\le 10000$
3	9	$0\le R_i\le 1$，对所有 $1\le i\le N$
4	38	$1\le N\le 75000$
5	42	无额外限制

子任务 5 含 5 个测试组，分值分别为 $7,8,8,9,10$。

样例

输入

9 3
2 5 4 3 2 1 8 7 3

输出

3 7 8

样例解释

矩阵 $A$ 为：

2 5 4
5 4 3
4 3 2
3 2 1
2 1 8
1 8 7
8 7 3

矩阵 $B$ 为：

2 4 5
3 4 5
2 3 4
1 2 3
1 2 8
1 7 8
3 7 8

矩阵 $B$ 三列的最大值分别为 $3,7,8$。