题目描述

给你一个长度为 $N$ 的数组，一个长为 $K$ 的滑动的窗体从最左移至最右端，你只能见到窗口的 $K$ 个数，每次窗体向右移动一位，如下表：

Window position           Min value            Max value 
[ 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

你的任务是找出窗口在各位置时的窗口内的最大元素和最小元素。

输入格式

第 $1$ 行 $n,k$ ，第 $2$ 行为长度为 $n$ 的数组

输出格式

2 行，第 1 行每个位置时窗口内的最小元素，第 2 行每个位置时窗口内的最大元素。

样例

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

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

数据范围

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