#include <cstdio>
#include <deque>
using namespace std;
const int maxn = 1000010;
deque <int> Max,Min;
int n,a[maxn],k,ansax[maxn],ansin[maxn];
void read(int &res){
	int x , f = 1;  char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;
	x = ch - 48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	res = x * f;
}
void Init(int i){
	while(!Max.empty() && a[Max.back()]<a[i]) Max.pop_back();
	while(!Min.empty() && a[Min.back()]>a[i]) Min.pop_back();
	Max.push_back(i);	Min.push_back(i);
}
void Work(){
	read(n);read(k);for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=k;i++)
		Init(i);
	ansax[k]=a[Max.front()]; ansin[k]=a[Min.front()];
	
	for(int i=k+1;i<=n;i++){
		Init(i);
		while(Max.front()<=i-k) Max.pop_front();
		while(Min.front()<=i-k) Min.pop_front();
		ansax[i] = a[Max.front()];
		ansin[i] = a[Min.front()];
	}
	
	for(int i=k;i<=n;i++)
		printf("%d ",ansin[i]);puts("");
	for(int i=k;i<=n;i++)
		printf("%d ",ansax[i]);puts("");
}
int main(){
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	Work(); return 0;
}
/*
10 4
-3 -3 4 9 6 -1 7 9 4 9
*/