#include <bits/stdc++.h>
using namespace std;
int n,k,q[1000001],e[1000001];
int head=0,tail=0;
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>k;
	q[head]=0;
	for (int i = 0; i < n; ++i)
	{
		cin>>e[i];
	}
	if(k==1)
	for (int i = 0; i < n; ++i)
	{
		cout<<e[i]<<" ";
	}
	else
	for (int i = 0; i < n; ++i)
	{
		if (i-q[head]>=k)
		{
			head++;
		}
		while((head<=tail)&&(e[q[tail]]>e[i])) tail--;
		tail++;
		q[tail]=i;
		if(i>=k-1)cout<<e[q[head]]<<" ";
	}
	cout<<endl;
	head=0,tail=0;
	if(k==1)
	for (int i = 0; i < n; ++i)
	{
		cout<<e[i]<<" ";
	}
	else
	for (int i = 0; i < n; ++i)
	{
		if (i-q[head]>=k)
		{
			head++;
		}
		while((head<=tail)&&(e[q[tail]]<e[i])) tail--;
		tail++;
		q[tail]=i;
		if(i>=k-1)cout<<e[q[head]]<<" ";
	}
	return 0;
}