Description

有$n$$（$$n$$≤$$10^6$$）$个元素的数组，以及一个大小为$k$的滑动窗口，将滑动窗口从数组的最左边移动到最右边，只可以在该窗口中看到$k$个数字，滑动窗口每次都向右移动一个位置，请确定滑动窗口在每个位置的最大值和最小值。

下面是一个例子，数组是$[$$1$ $3$ -$1$ -$3$ $5$ $3$ $6$ $7$$]$，$k$是$3$。

Format

Input

第$1$行包含整数$n$和$k$，表示元素个数和滑动窗口的长度；第$2$行包含$n$个整数。

Output

第$1$行从左到右分别输出每个窗口中的最小值，第$2$行输出最大值。

Samples

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

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