#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 1000005

struct QueueType {

    int x,dis;

};

struct QueueType mique[maxn],maque[maxn],ai[maxn];

int n,k,mihead,mitail=-,mahead,matail=-;

inline void in(int &now)

{

    int if_z=;now=;

    char Cget=getchar();

    while(Cget>''||Cget<'')

    {

        if(Cget=='-') if_z=-;

        Cget=getchar();

    }

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

    now*=if_z;

}

int main()

{

    in(n),in(k);

    for(int i=;i<=n;i++) in(ai[i].dis),ai[i].x=i;

    for(int i=;i<k;i++)

    {

        mique[++mitail]=ai[i];

        while(mitail>mihead)

        {

            if(mique[mitail].dis<=mique[mitail-].dis) mique[mitail-]=mique[mitail--];

            else break;

        }

        maque[++matail]=ai[i];

        while(matail>mahead)

        {

            if(maque[matail].dis>=maque[matail-].dis) maque[matail-]=maque[matail--];

            else break;

        }

    }

    for(int i=k;i<=n;i++)

    {

        mique[++mitail]=ai[i];

        while(mitail>mihead)

        {

            if(mique[mitail].dis<=mique[mitail-].dis) mique[mitail-]=mique[mitail--];

            else break;

        }

        printf("%d ",mique[mihead].dis);

        if(mique[mihead].x==i-k+) mihead++;

    }

    printf("\n");

    for(int i=k;i<=n;i++)

    {

        maque[++matail]=ai[i];

        while(matail>mahead)

        {

            if(maque[matail].dis>=maque[matail-].dis) maque[matail-]=maque[matail--];

            else break;

        }

        printf("%d ",maque[mahead].dis);

        if(maque[mahead].x==i-k+) mahead++;

    }

    return ;

}