题目描述

有一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，以及一个长度为 $k$ 的窗口。

窗口从序列的最左端开始，每次向右滑动一格，直到窗口的右端到达 $n$。显然一共有 $n-k+1$ 个窗口位置。

请你求出每个窗口中的最小值和最大值。

输入格式

第一行两个整数 $n,k$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

输出两行，每行 $n-k+1$ 个整数，相邻两个数之间用一个空格隔开。

第一行是每个窗口的最小值。

第二行是每个窗口的最大值。

输入输出样例 #1

输入 #1

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

输出 #1

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

说明

数据范围

• 对于 $100\%$ 的数据，$1\le k\le n\le 5\times 10^5$，$|a_i|\le 10^9$。