#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n,k,a[N],qmin[N],head=1,tail,pos[N],l[N],cnt=0;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		while(head<=tail&&a[i]<=qmin[tail]) tail--;
		qmin[++tail]=a[i],pos[tail]=i;
		if(i>=k){ if(i-pos[head]+1>k){head++;}cout<<qmin[head]<<" ";}
	} cout<<endl;
    head=1,tail=0;
    for(int i=1;i<=n;i++){
        while(head<=tail&&a[i]>=qmin[tail]) tail--;
        qmin[++tail]=a[i];
        pos[tail]=i;
        if(i>=k){
        	if(i-pos[head]+1>k){head++;}
        	cout<<qmin[head]<<" ";
		}
    }
}