#include<iostream>
#include<algorithm>
using namespace std;
int const maxn=1000010;
int a[maxn],q[maxn];///q[]里面存的是数组的下标

int main(void)
{
    int n,k;
    cin>>n>>k;
    int hh=0;int tt=-1;
    for(int i=0;i<n;i++)  cin>>a[i];
    for(int i=0;i<n;i++)
    {
        if(hh<=tt&& i-k+1>q[hh]) hh++;

        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;   ///注意是while ,所以后面进来的比前面小的会被送到队头
        q[++tt]=i;

        if(i>=k-1) cout<<a[q[hh]]<<" ";  ///当窗口到下一个周期k时,队列里的队头存的是最小值的下标
    }
    cout<<endl;
    hh=0;tt=-1;
    for(int i=0;i<n;i++)
    {
         if(hh<=tt&&i-k+1>q[hh]) hh++;

         while(hh<=tt&&a[q[tt]]<=a[i]) tt--;
         q[++tt]=i;
         if(i>=k-1) cout<<a[q[hh]]<<" ";
    }
    cout<<endl;
return 0;    
}