#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000001];
deque<int> q;
void do_min() {
	for(int i=1;i<=n;i++) {
		while(!q.empty()&&a[q.back()]>a[i]) {
			q.pop_back();
		}
		q.push_back(i);
		while(!q.empty()&&i-q.front()>k) {
			q.pop_front();
		}
		if(i>=k) {
			cout<<a[q.front()]<<' ';
		}
	}
	cout<<'\n';
	return;
}
void do_max() {
	for(int i=1;i<=n;i++) {
		while(!q.empty()&&a[q.back()]<a[i]) {
			q.pop_back();
		}
		q.push_back(i);
		while(!q.empty()&&i-q.front()>k) {
			q.pop_front();
		}
		if(i>=k) {
			cout<<a[q.front()]<<' ';
		}
	}
	return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
	}
	do_min();
	while(!q.empty()) {
		q.pop_front();
	}
	do_max();
	return 0;
}