题目描述

在一个包含$\red{n}$个元素的数组上，有一个长度为$\red{k}$的窗户在从左向右滑动。窗户每滑动到一个位置，我们都可以看到$\red{k}$个元素在窗户中。如下的例子所示，假设数组为 $\red{[1 3 -1 -3 5 3 6 7]，}$而$\red{k}$等于$\red{3:}$

对于窗户滑动过的每个位置，请给出窗户内$\red{k}$个元素的最小值和最大值。

输入格式

输入的第一行包括两个整数$\red{n，}$$\red{k，}$$\red{n}$表示数组的长度，$\red{k}$表示窗户的长度。

接下来一行包括$\red{n}$个整数，表示这个$\red{n}$个元素的数组。

输出格式

输出包含两行，每行包括$\red{n-k+1}$个整数，第一行表示窗户从左到右滑动过程中的最小值，第二行表示窗户从左到右滑动过程中的最大值。

样例

输入样例

8 3
1 3 -1 -3 5 3 6 7

输出样例

-1 -3 -3 -3 3 3
3 3 5 5 6 7

提示

对于$\red{100\%}$的数据，$\red{3<=n<=1000000，}$$\red{1<=k<=n，}$数组中的每个元素均在$\red{int}$范围内