Description

给定一个大小为n（n ≤ 106）的数组。现在有一个大小为k的滑动窗口，从数组的最左边滑动到数组的最右边。在窗口中你只能看见k个数字，每次窗口会向右移动一个位子。以下是一个实例：
数组{1 3 -1 -3 5 3 6 7}，且k = 3 .




你的任务就是确认滑动窗口在每个位置的最小值和最大值。
 

Input

多组数据，以文件控制结束
第一行输入两个整数n，k，（k ＜ n）分别表示数组的长度和窗口大小。
第二行输入n个整数，ai（0 ≤ i ＜ n）在int范围内。

Output

每组数据输出分两行。
第一行输出窗口在每个位置时的最小值。
第二行输出窗口在每个位置时的最大值。两个数之间用空格分开，最后一个数直接换行。

Sample Input

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

Sample Output

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

HINT

输入输出数据过大，用scanf、printf代替cin、cout

Source

POJ