#include<bits/stdc++.h>
using namespace std;
int n,m,i,a[1001000],ans1[1001000],ans2[1001000],t2,h1,h2,t1,t3,q1[1001000],q2[1001000];
int main(){
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	h1=t1=h2=t2=1;
	q1[1]=q2[1]=1;
	if (m==1) ans1[1]=ans2[2]=a[1];
	for (i=2;i<=n;i++){
		while (h1<=t1&&a[i]<=a[q1[t1]]) --t1;
		q1[++t1]=i;
		while (h2<=t2&&a[i]>=a[q2[t2]]) --t2;
		q2[++t2]=i;
		while (h1<=t1&&q1[h1]+m<=i) ++h1;
		while (h2<=t2&&q2[h2]+m<=i) ++h2;
		ans1[i]=a[q1[h1]],ans2[i]=a[q2[h2]];
	}
	for (i=m;i<=n;i++) printf("%d ",ans1[i]);puts("");
	for (i=m;i<=n;i++) printf("%d ",ans2[i]);

}