using namespace std;
#include<bits/stdc++.h>
#define ll long long
const int N=1e5+7;
ll read(){
   ll summ=0;ll f=1;char ch;
   ch=getchar();
   while(ch<'0'||ch>'9'){
	   if(ch=='-'){
		   f=-1;
	   }
	   ch=getchar();
   
   }
   while(ch>='0'&&ch<='9'){
	   summ=summ*10+ch-'0';
	   ch=getchar();
   
   }
   return f*summ;

}
ll q[N]; ll n,k;ll ar[N];
ll h=1,t=0;
ll minn(){
	for(int i=1;i<=n;i++){
		while(h<=t && ar[q[t]]>=ar[i]) t--;
		q[++t]=i;
		if(q[h]<i-k+1) h++;
		if(i>=k) cout<<ar[q[h]]<<' ';
	}
	cout<<endl;
}
ll maxx(){
	for(int i=1;i<=n;i++){
		while(h<=t && ar[q[t]]<=ar[i]) t--;
		q[++t]=i;
		if(q[h]<i-k+1){
			h++;
		}
		if(i>=k) cout<<ar[q[h]]<<' ';
	}
	cout<<endl;
}
int main(){
 	n=read();k=read();
 	for(int i=1;i<=n;i++){
 		ar[i]=read();	
	 }
	memset(q,0,sizeof(q));

	minn();
	memset(q,0,sizeof(q));
	h=1;t=0;
	maxx();
	return 0;
}