#include <iostream>
using namespace std;

const int MAXN = 1000005;
int arr[MAXN];
int minRes[MAXN], maxRes[MAXN]; // 存储结果

// 单调队列（用数组实现）
int minQ[MAXN], maxQ[MAXN]; // 存储下标
int minHead, minTail; // 队首和队尾指针
int maxHead, maxTail;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 求最小值 - 单调递增队列
    minHead = 0;
    minTail = 0;
    int minCnt = 0;

    for (int i = 0; i < n; i++) {
        // 移除队首过期元素（不在窗口内）
        while (minHead < minTail && minQ[minHead] < i - k + 1) {
            minHead++;
        }

        // 维护单调性：移除队尾所有≥当前元素的值
        while (minHead < minTail && arr[minQ[minTail - 1]] >= arr[i]) {
            minTail--;
        }

        // 当前元素入队
        minQ[minTail++] = i;

        // 窗口形成后记录答案
        if (i >= k - 1) {
            minRes[minCnt++] = arr[minQ[minHead]];
        }
    }

    // 求最大值 - 单调递减队列
    maxHead = 0;
    maxTail = 0;
    int maxCnt = 0;

    for (int i = 0; i < n; i++) {
        // 移除队首过期元素
        while (maxHead < maxTail && maxQ[maxHead] < i - k + 1) {
            maxHead++;
        }

        // 维护单调性：移除队尾所有≤当前元素的值
        while (maxHead < maxTail && arr[maxQ[maxTail - 1]] <= arr[i]) {
            maxTail--;
        }

        // 当前元素入队
        maxQ[maxTail++] = i;

        // 窗口形成后记录答案
        if (i >= k - 1) {
            maxRes[maxCnt++] = arr[maxQ[maxHead]];
        }
    }

    // 输出最小值
    for (int i = 0; i < minCnt; i++) {
        if (i > 0) cout << " ";
        cout << minRes[i];
    }
    cout << "\n";

    // 输出最大值
    for (int i = 0; i < maxCnt; i++) {
        if (i > 0) cout << " ";
        cout << maxRes[i];
    }
    cout << "\n";

    return 0;
}