#include<iostream>
#include<cstdio>
#include<cctype>
#include<deque>
using namespace std;
const int maxn=1000010;
int n,k;
int a[maxn],amax[maxn],amin[maxn];
deque<int> dqmax;
deque<int> dqmin;
inline void in(int &x){
    x=0;int f=1;char t=getchar();
    while(!isdigit(t)){if(t=='-')f=-1;t=getchar();}
    while(isdigit(t)){x=x*10+t-48;t=getchar();}
    x*=f;
}
inline void insertmin(int x){
	while(!dqmin.empty()&&a[x]<a[dqmin.back()]){
		dqmin.pop_back();
	}
	dqmin.push_back(x);
}
inline void insertmax(int x){
	while(!dqmax.empty()&&a[x]>a[dqmax.back()]){
		dqmax.pop_back();
	}
	dqmax.push_back(x);
}
inline int qmin(int x,int k){
	while(dqmin.front()<(x-k+1)){
		dqmin.pop_front();
	}
	return dqmin.front();
}
inline int qmax(int x,int k){
	while(dqmax.front()<(x-k+1)){
		dqmax.pop_front();
	}
	return dqmax.front();
}
inline int work(){
	in(n);in(k);
	for(int i=1;i<=n;i++) in(a[i]);
	for(int i=1;i<=k;i++){
		insertmin(i);insertmax(i);
	}
	for(int i=k;i<=n;i++){
		insertmin(i);insertmax(i);
		amin[i]=a[qmin(i,k)];
		amax[i]=a[qmax(i,k)];
	}
	for(int i=k;i<=n;i++) printf("%d ",amin[i]);printf("\n");
	for(int i=k;i<=n;i++) printf("%d ",amax[i]);printf("\n");
}
inline int mian(){
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	work();
}
int miku=mian();
int main(){;}