#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int q[N];
int a[N];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt&&i-q[hh]+1>k) hh++; //超过窗口个数
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--; //当前元素更小
        q[++tt]=i; //入队
        if(i>=k) cout<<a[q[hh]]<<" "; //最小值
    }
    cout<<endl;
    hh=0,tt=-1; //同理计算最大值
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt&&i-q[hh]+1>k) hh++;
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
        q[++tt]=i;
        if(i>=k) cout<<a[q[hh]]<<" ";
    }
    return 0;
}