#include<iostream>
using namespace std;

const int N = 1000010;
int maxq[N], minq[N];
int hh = 1, tt = 0;
int n, k;
int a[N];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    //开始先输出最小值
    //队尾入队，队尾淘汰，队头出队
    for (int i = 1; i <= n; i ++ ) {
        while(tt >= hh && a[minq[tt]] >= a[i]) tt -- ;
        minq[ ++ tt] = i;
        if (minq[hh] < i - k + 1) hh ++ ;
        if (i >= k) cout << a[minq[hh]] << " ";
    }
    cout << endl;

    //输出最大值
    //队尾入队，队尾淘汰，队头出队
    tt = 0, hh = 1;
    for (int i = 1; i <= n; i ++ ) {
        while(tt >= hh && a[maxq[tt]] <= a[i]) tt -- ;
        maxq[ ++ tt] = i;
        if (maxq[hh] < i - k + 1) hh ++ ;
        if (i >= k) cout << a[maxq[hh]] << " ";
    }
}