C++ :

#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
deque<int> q_max,q_min;
int n,k,a[1000001];
int b[1000001],c[1000001];
void insert(int,bool);
void init();
void work();
int main()
{
	//freopen("window6.in","r",stdin);
	//freopen("window.out","w",stdout);
	init();
	work();
	return 0;
}
void init()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];	
}
void work()
{
	
	for(int i=1;i<k;i++)
	{
		insert(i,0);
		insert(i,1);
	}	
	for(int i=k;i<=n;i++)
	{
		insert(i,0);
		insert(i,1);		
		while(!q_max.empty()&&q_max.front()<i-k+1) q_max.pop_front();
		while(!q_min.empty()&&q_min.front()<i-k+1) q_min.pop_front();
		b[i]=a[q_max.front()];
		c[i]=a[q_min.front()];
	}
	for(int i=k;i<n;i++) cout<<c[i]<<' ';cout<<c[n]<<endl;
	for(int i=k;i<n;i++) cout<<b[i]<<' ';cout<<b[n]<<endl;
}
void insert(int x,bool f)
{	
	if(f)
	{
		while(!q_max.empty() && a[q_max.back()]<=a[x]) q_max.pop_back();
		q_max.push_back(x);
	}
	else
	{
		while(!q_min.empty() && a[q_min.back()]>=a[x]) q_min.pop_back();
		q_min.push_back(x);
	}
}