#include<iostream>
#include<stack>
using namespace std;
int n,m;
int qmin[1000005],qmax[1000005],a[1000005];
int min_deque(){
	int h=1,t=1;
	for(int i=1;i<=n;i++){
		while(h <=t && qmin[h]+m <= i){
			h++;
		}
		while(h <=t && a[i] <= a[qmin[h]]){
			t--;
		}
		qmin[++t]=i;
		if(i >= m){
			cout<<a[qmin[h]]<<' ';
		}
	}
	cout<<endl;
	return 0;
}
int max_deque(){
	int h=1,t=0;
	for(int i=1;i<=n;i++){
		while(h <=t && qmax[h]+m <= i){
			h++;
		}
		while(h <=t && a[i] >= a[qmax[h]]){
			t--;
		}
		qmax[++t]=i;
		if(i >= m){
			cout<<a[qmax[h]]<<' ';
		}
	}
	return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	min_deque();
	max_deque();
}