#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N];
int q[N];//存储的是下标 
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int tt=-1,hh=0;
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt && q[hh]<i-k+1 )hh++;//保证队首元素的下标在队列中，队首元素出队 
        while(hh<=tt && a[q[tt]]>=a[i])tt--;
        //for(int j=hh;j<=tt;j++)cout<<a[q[j]]<<' ';
        //cout<<endl;
        q[++tt]=i;
        if(i>k-1)printf("%d ",a[q[hh]]);
    }
    printf("\n");
    tt=-1,hh=0;
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt && q[hh]<i-k+1)hh++;
        while(hh<=tt && a[q[tt]]<=a[i])tt--;
        q[++tt]=i;
        if(i>k-1)printf("%d ",a[q[hh]]);
    }
    return 0;
}