#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int nums[N],q[N],head=0,rear=-1;

int main(){
    int n,k;
    cin >> n >> k;
    for (int i = 0;i< n ;i++){
        cin >> nums[i];
    }

    for(int i = 0 ; i< n ;i++){
        if (i-k>=0 && q[head]==i-k){
            head++;
        }
        while(head <= rear && nums[q[rear]] >= nums[i]){
            rear--;
        }
        q[++rear]=i;
        if (i+1>=k){
            cout << nums[q[head]] << ' ';
        }
    }
    cout << '\n';
    head=0,rear=-1;

    for (int i = 0 ;i< n ;i++){
        if (i-k>=0 && q[head]==i-k){
            head++;
        }
        while(head <= rear && nums[q[rear]] <= nums[i]){
            rear--;
        }
        q[++rear]=i;
        if (i+1>=k){
            cout << nums[q[head]] << ' ';
        }
    }
    return 0;
}