题目描述

给定一个长度为n的数组a。

有一个大小为k的滑动窗口（窗口中只能看到k个元素），它从数组的最左边，每次向右移动一个位置，直到移动到最右边。

你需要回答出滑动窗口在每个位置时，窗口中的最大值和最小值。

例如，对于数组 { 0,3,1,0,-5,2,1,8 }，窗口大小为3，窗口在不同位置处的情况如下：

输入描述

第一行：两个整数n,k。（1 \le k \le n \le 2 \times 10^5）

第二行：n个整数，代表数组a。（-10^6 \le a_i \le 10^6，1 \le i \le n）

输出描述

第一行：从左到右，滑动窗口在每个位置的最大值。

第二行：从左到右，滑动窗口在每个位置的最小值。

输入样例1

8 3
0 3 1 0 -5 2 1 8

输出样例1

3 3 1 2 2 8
0 0 -5 -5 -5 1