#include<bits/stdc++.h>
using namespace std;
inline int QR(){
	char ch;
	bool minus=0;
	while(!isdigit(ch=getchar())) if(ch=='-') minus=1;
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	if(minus) return -x;
	return x;
}
inline void QW(long long num){
	if(num<0) num=-num,putchar('-');
	int cnt=0;
	string str;
	while(str[++cnt]=num%10+'0',num/=10,num);
	while(putchar(str[cnt]),--cnt,cnt);
	putchar(' ');//数字之后的输出
}

const int maa=1e6+10;
int sum[maa]={0},ma[maa]={0},mi[maa]={0};
deque<int> q1,q2;
void insert(int);
int main(){
	#define OJ
	#ifdef OJ
		freopen("window.in","r",stdin);
		freopen("window.out","w",stdout);
	#endif
	int n=QR(),k=QR();
	for(int i=1;i<=n;i++) sum[i]=QR();
	for(int i=1;i<=k;i++) insert(i);
	for(int i=k;i<=n;i++){
		insert(i);
		if(!q1.empty()&&q1.front()<i-k+1) q1.pop_front();
		if(!q2.empty()&&q2.front()<i-k+1) q2.pop_front();
		ma[i]=q1.front();mi[i]=q2.front();
	}
	for(int i=k;i<=n;i++) QW(sum[mi[i]]);
	putchar('\n');
	for(int i=k;i<=n;i++) QW(sum[ma[i]]);
	putchar('\n');
	return 0;
}
void insert(int x){
	while(!q1.empty() && sum[x]>=sum[q1.back()]) q1.pop_back();
	q1.push_back(x);
	while(!q2.empty() && sum[x]<=sum[q2.back()]) q2.pop_back();
	q2.push_back(x);
}