#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, k, a[N], q[N], hh = -1, tt = 0;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i ++) cin >> a[i];

    for (int i = 0; i < n; i ++) {
        if (tt <= hh && i - k >= q[tt]) tt ++;
        while (tt <= hh && a[i] <= a[q[hh]]) hh --;
        q[++hh] = i;
        if (i >= k - 1) {
            cout << a[q[tt]] << ' ';
        }
    }

    cout << endl;

    hh = -1, tt = 0;
    for (int i = 0; i < n; i ++) {
        if (tt <= hh && i - k >= q[tt]) tt ++;
        while (tt <= hh && a[i] >= a[q[hh]]) hh --;
        q[++hh] = i;
        if (i >= k - 1) {
            cout << a[q[tt]] << ' ';
        }
    }
    cout << endl;
}