#include <stdio.h>
#include <algorithm>

int max[1000000],min[1000000];//1000000


int a[1000010];//1000010
int que[1000100]={0};//1000100

inline void minnum(int n,int k)
{
    int front=0,rear=0;
    int j=0,l=0;
    que[rear++]=j++;
    while(j<k)
    {
        if(a[que[rear-1]]<a[j])
            que[rear++]=j;
        else
        {
            while(a[j]<=a[que[rear-1]] && front<rear)//如果有个值比最前面的数大，但比它前面数小
                rear--;
            if(a[que[front]]>=a[j] && rear-front==1)//如果值比最前面的数小
                rear--;
            que[rear++]=j;
        }
        j++;
    }
    min[l++]=a[que[front]];
    if(j-que[front]>=k)
            front++;
    while(j<n)
    {
        //如果数组的值大于队列的值，则放入队列
        //否则这个数前面的值都出队列，再将其放入队列
        //如果队列第一个值已经出了k的范围，则出队列
        if(a[que[rear-1]]<a[j])
            que[rear++]=j;
        else
        {
            while(a[que[rear-1]]>=a[j] && front<rear)//如果有个值比最前面的数大，但比它前面数小
                rear--;
            if(a[que[rear-1]]>=a[j] && rear-front==1)//如果这个值比最前面的数小
                rear--;
            que[rear++]=j;
        }
        min[l++]=a[que[front]];
        j++;
        if(j-que[front]>=k)
            front++;
    }
}

inline void maxnum(int n,int k)
{
    int j=0,front=0,rear=0,l=0;
    que[rear++]=j++;
    while(j<k)
    {
        if(a[que[rear-1]]>a[j])
            que[rear++]=j;
        else
        {
            while(a[j]>=a[que[rear-1]] && front<rear)//如果有个值比最前面的数小，但比它前面数大
                rear--;
            if(a[que[front]]<=a[j] && rear-front==1)//如果这个值还比最前面的大
                rear--;
            que[rear++]=j;
        }
        j++;
    }
    max[l++]=a[que[front]];
    if(j-que[front]>=k)
            front++;
    while(j<n)
    {
        if(a[que[rear-1]]>a[j])
            que[rear++]=j;
        else
        {
            while(a[que[rear-1]]<=a[j] && front<rear)//如果有个值比最前面的数小，但比它前面数大
                rear--;
            if(a[que[rear-1]]<=a[j] && front-rear==1)//如果这个值比最前面的数大
                rear--;
            que[rear++]=j;
        }
        max[l++]=a[que[front]];
        j++;
        if(j-que[front]>=k)
            front++;
    }
}

int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    int i;
    for(i=0;i<m;i++)
        scanf("%d",&a[i]);
    minnum(m,n);
    maxnum(m,n);
    for(i=0;i<m-n;i++)
        printf("%d ",min[i]);
    printf("%d\n",min[m-n]);
    for(i=0;i<m-n;i++)
        printf("%d ",max[i]);
    printf("%d",max[m-n]);

    return 0;
}