问题描述

给定一个长度为 $N$ 的序列 $a$ 与一个长度为 $K$ 的窗口。$(1\le K\le N)$

该窗口会从序列的最左端滑动到最右端，你需要输出 $2$ 行，每行 $N-K+1$ 个数字。

第 $1$ 行为每个窗口的最小值。

第 $2$ 行为每个窗口的最大值。

输入格式

第一行输入两个正整数 $N,K$。$(1\le K\le N\le 10^5)$

第二行输入 $N$ 个正整数，表示序列 $a$。$(1\le a_i\le 10^5)$

输出格式

输出 $2$ 行，每行 $N-K+1$ 个数字。

第 $1$ 行为每个窗口的最小值。

第 $2$ 行为每个窗口的最大值。

样例输入

8 3
1 3 1 3 5 3 6 7

样例输出

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