给定一个长度为n（n ≤ 10^6）的数组，有一个大小为k的滑动窗口从数组的最左端移动到最右端，每次向右滑动一个位置，求窗口在每个位置时的最大值和最小值。

示例：数组为 [1, 3, -1, -3, 5, 3, 6, 7]，k = 3，窗口移动过程如下： | 窗口位置 | 最小值 | 最大值 | | --- | --- | --- | | [1 3 -1] -3 5 3 6 7 | -1 | 3 | | 1 [3 -1 -3] 5 3 6 7 | -3 | 3 | | 1 3 [-1 -3 5] 3 6 7 | -3 | 5 | | 1 3 -1 [-3 5 3] 6 7 | -3 | 5 | | 1 3 -1 -3 [5 3 6] 7 | 3 | 6 | | 1 3 -1 -3 5 [3 6 7] | 3 | 7 |

时间限制：20000ms 内存限制：65536KB

输入

输入共两行： 第一行包含两个整数n和k，分别表示数组长度和窗口大小。 第二行包含n个整数，表示数组元素。

输出

输出共两行： 第一行是每个窗口位置的最小值，空格分隔。 第二行是每个窗口位置的最大值，空格分隔。

样例输入

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

样例输出

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