/*
滑动窗口——经典利用单调队列解决，用一个dequeue双端队列维护一个单调队列，队列中存储数组的索引
存储索引便于判断滑动窗口是否超出滑过而弹出队头元素
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N = 1000010;
int a[N];
deque<int>windowslide;
int n, k;

void findMin(){
    //维护一个单调递减队列， 使得队头始终为滑动窗口的最小值
    windowslide.clear();
    for(int i = 0; i < n; i++){
        while( !windowslide.empty() && a[windowslide.back()] > a[i] )windowslide.pop_back();
        //若windowslide不满足单调递增，则弹出队尾元素
        while( !windowslide.empty() && i - windowslide.front() >= k )windowslide.pop_front();
        //若windowslide已滑过，则弹出队头一个元素
        windowslide.push_back(i);//添加元素
        if(i >= k - 1)cout << a[windowslide.front()] << ' ' ;//输出
    }
}

void findMax(){
    //维护一个单调递减队列， 使得队头始终为滑动窗口的最大值
    windowslide.clear();
    for(int i = 0; i < n; i++){
        while( !windowslide.empty() && a[windowslide.back()] < a[i])windowslide.pop_back();
        //若windowslide不满足单调递减，则弹出队尾元素
        while( !windowslide.empty() && i - windowslide.front() >= k)windowslide.pop_front();
        //若windowslide已滑过，则弹出队头一个元素
        windowslide.push_back(i);//add
        if(i >= k - 1)cout << a[windowslide.front()] << ' ';//output
    }
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    findMin();//找出滑动窗口的最小值
    cout << endl;
    findMax();//找出滑动窗口的最大值
}