#include <cstdio>
#include <deque> 
using namespace std;

const int maxN=1000005,inf=0x3f3f3f3f;
int a[maxN],n,k;
deque<int> ma,mi;
void getmax() 
{
	a[0]=-inf;
	ma.push_back(0);
	for (int i = 1; i <= n; i++)
	{
		if (a[i]<=a[ma.back()])	ma.push_back(i);
		else {do{ma.pop_back();}while (!ma.empty()&&a[ma.back()]<a[i]);ma.push_back(i);}		
		if (i-ma.front()+1>k) ma.pop_front();	
		if (i>=k)
		{
			printf("%d",a[ma.front()]);	
			if (i<n) putchar(' ');
		}		
	}
	puts("");
}

void getmin() 
{
	a[0]=inf;
	mi.push_back(0);
	for (int i = 1; i <= n; i++)
	{
		if (a[i]>=a[mi.back()])	mi.push_back(i);
		else {do{mi.pop_back();}while (!mi.empty()&&a[mi.back()]>a[i]);mi.push_back(i);}	
		if (i-mi.front()+1>k) mi.pop_front();	
		if (i>=k)
		{
			printf("%d",a[mi.front()]);		
			if (i<n) putchar(' ');
		}		
	}
	puts("");
}

void read()
{
	scanf("%d%d",&n,&k);
	for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
}

int main()
{
//	freopen("D:\\input.txt","r",stdin);
	read();
	getmin();
	getmax();	
	return 0;
}//poj Accepted	7196K	10016MS