//洛谷 P1886
#include<bits/stdc++.h>
using namespace std;

int q1[1000005],q2[1000005];

int a[1000005];

int n,k;

int min_deque(){
	int t=1,w=0;
	for(int i=1;i<=n;++i){
		while(t<=w && q1[t]+k<=i)  t++;
		
		while(t<=w && a[i]<a[q1[w]])  w--;
		
		q1[++w]=i;
		
		if(i>=k)  cout<<a[q1[t]];
	}
	cout<<endl;
}
int max_deque(){
	int t=1,w=0;
	for(int i=1;i<=n;++i){
		while(t<=w && q2[t]+k<=i)  t++;
		
		while(t<=w && a[i]<a[q2[w]])  w--;
		
		q2[++w]=i;
		
		if(i>=k)  cout<<a[q2[t]];
	}
	cout<<endl;
}

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;++i)  cin>>a[i];
	min_deque();
	max_deque();
	return 0;
}