#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define maxn___maxn 1000000
struct dequeue{
	int a[1000010];
	int f,b,len;
	dequeue(){f=0;b=1;len=0;}
	void push_front(int x){f++;len++;if(f>maxn___maxn)f=0;a[f]=x;}
	void push_back(int x){b--;len++;if(b<0)b=maxn___maxn;a[b]=x;}
	void pop_front(){f--;len--;if(f<0)f=maxn___maxn;}
	void pop_back(){b++;len--;if(b>maxn___maxn)b=0;}
	int front(){return a[f];}
	int back(){return a[b];}
	bool empty(){return len==0;}
};
struct duque{
	int n,l,iq;
	int arrage[1000010];
	int maxn[1000010],minn[1000010];
	//deque<int>q;
	duque(){iq=0;}
	dequeue p,q;
	void check(int place){
		while(!q.empty()&&arrage[q.back()]<=arrage[place]){q.pop_back();}q.push_back(place);
		while(!p.empty()&&arrage[p.back()]>=arrage[place]){p.pop_back();}p.push_back(place);
	}
	void watch(){
		for(int i=1;i<l;i++)check(i);
		minn[++iq]=q.front();maxn[iq]=p.front();
		for(int i=l;i<=n;i++){
			check(i);
			while(!q.empty()&&q.front()<i-l+1)q.pop_front();
			while(!p.empty()&&p.front()<i-l+1)p.pop_front();
			minn[++iq]=q.front();maxn[iq]=p.front();
		}
		for(int i=2;i<=iq;i++)printf("%d ",arrage[maxn[i]]);printf("\n");
		for(int i=2;i<=iq;i++)printf("%d ",arrage[minn[i]]);
	}
	int doing(){scanf("%d %d",&n,&l);
		if(l>n)l=n;
		for(int i=1;i<=n;i++){scanf("%d",&arrage[i]);}
		watch();
		return 0;
	}
}arcv;
FILE*_=freopen("window.in","r",stdin);
FILE*__=freopen("window.out","w",stdout);
int a=arcv.doing();
int main(){;}