题目描述

有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：数组为\([1,3,-1,-3,5,3,6,7]\), 且\(k = 3\)。

\(\text{Window~position}\)	\(\text{Minimum~value}\)	\(\text{Maximum~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\)

格式

输入格式

输入一共有两行，第一行有两个正整数 \(n,k\)。
第二行 \(n\) 个整数，表示序列 \(a\)。

输出格式

输出共两行，第一行为每次窗口滑动的最小值。

第二行为每次窗口滑动的最大值。

样例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 10^6\)，\(a_i \in [-2^{31},2^{31})\)。