题目描述

自助餐，亦称顿饭，有时亦称冷餐会，它是国际上所通行的一种非正式的西式宴会，在大型的[商务活动]中尤为多见。它的具体作法是，不预备正餐，而由就餐者随意在用餐时自行选择食物、饮料，然后或立或坐，自由地与他人在一起或是独自一人地用餐。自助餐之所以称为自助餐，主要是因其可以在用餐时调动用餐者的主观能动性而由其自己动手，自己帮助自己，自己在既定的范围之内安排选用菜肴。

现在一家甜点餐厅推出了他们自助餐的规则，有n个甜点排成一排，顾客可以任意选择其中连续的k个甜点中价值最高的和价值最低的2个甜点，每日摆盘结束后，餐厅需要计算出每种选择情况下的最小值和最大值。

例如 甜点排序后对应价格是【1，3，-1，-3，5，3，6，7】，k=3，可供选择为【1，3，-1】、【3，-1，-3】、【-1，-3，5】、【-3，5，3】、【5，3，6】、【3，6，7】，现在需要从第一种开始到最后一种，按顺序把每种选择中的最小值和最大值甜点分别求出来。

输入格式

输入一共有两行，第一行有两个正整数 $n,k$。 第二行 $n$ 个整数，表示序列 $a$

输出格式

输出共两行，第一行为每次选择的最小值 第二行为每次选择的最大值

样例 #1

样例输入 #1

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

样例输出 #1

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

提示

【数据范围】 对于 $50\%$ 的数据，$1 \le n \le 10^5$；

对于 $100\%$ 的数据，$1\le k \le n \le 10^6$，$a_i \in [-2^{31},2^{31})$。