#include <iostream>

using namespace std;

const int N = ;

int a[N], q[N];//a是原来的值，q是队列 存的是下标

int main() {

    int n, k;

    scanf("%d%d", &n, &k);

    for (int i = ; i < n; i ++ ) scanf("%d", &a[i]);

    int hh = , tt = -;  //定义队头和队尾，开始是空的

    for (int i = ; i < n; i ++ ) {  //i是右端点

        //因为每次最多只有一个数字不在窗口内，所以只需要移动一个，也就是用if

        //判断队头是否已经滑出了窗口，先判断是不是空的

        if (hh <= tt && i - k +  > q[hh])  //终点是i，起点是i-k+1 ，如果起点大于q【hh】，说明已经滑出窗口

            hh ++ ;//队头加一 ，加以之后，之前的数字就不会再被用到

        while (hh <= tt && a[q[tt]] >= a[i])

            tt -- ; //如果准备插入的数字比队尾的小，那么队尾的就没有用了，那么就把队尾的删掉，会一直删除，直到，不满足hh <= tt，队列变为空

            //虽然会删除，但不会改变滑动窗口的长度，因为滑动窗口是根据下标来移动的

            //如果准备插入的数字比队尾的大，就不用删除，直接插进去 ，最终会单调递增

        q[ ++ tt] = i;//再把当前的数字插进去，放到队尾，如果之前的删除使队列变为空，因为+1，所以会多一个

        if (i >= k - ) printf("%d ", a[q[hh]]);//因为队头一定会是最小的，所以，输出队头

    }

    puts("");

    hh = , tt = -;

    for (int i = ; i < n; i ++ ) {

        if (hh <= tt && i - k +  > q[hh]) hh ++ ;

        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;

        q[ ++ tt] = i;

        if (i >= k - ) printf("%d ", a[q[hh]]);

    }

    puts("");

    return ;

}