#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
	int x,y;
}v[1110000];
int m,n,mx[1110000],mn[1110000],a[1110000];
void getmin()
{
	int i,head=1,tail=0;
	for(i=1;i<m;i++)
	{
		while(head<=tail&&v[tail].x>=a[i])tail--;
		v[++tail].x=a[i];v[tail].y=i;
	}
	for(;i<=n;i++)
	{
		while(head<=tail&&v[tail].x>=a[i])tail--;
		v[++tail].x=a[i];v[tail].y=i;
		while(v[head].y<i-m+1)head++;
		mn[i-m+1]=v[head].x;
	}
}
void getmax()
{
	int i,head=1,tail=0;
	for(i=1;i<m;i++)
	{
		while(head<=tail&&v[tail].x<=a[i])tail--;
		v[++tail].x=a[i];v[tail].y=i;
	}
	for(;i<=n;i++)
	{
		while(head<=tail&&v[tail].x<=a[i])tail--;
		v[++tail].x=a[i];v[tail].y=i;
		while(v[head].y<i-m+1)head++;
		mx[i-m+1]=v[head].x;
	}
}
int main()
{
	int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	getmin();
	getmax();
	for(i=1;i<=n-m+1;i++)printf("%d ",mn[i]);
	printf("\n");
	for(i=1;i<=n-m+1;i++)printf("%d ",mx[i]);
	printf("\n");
	return 0;
}