#include <stdio.h>
 #include <string.h>
 #include <iostream>
 using namespace std;
 
 #define N 1000010
 
 struct node{
     int m, d;
 }Inc[N], Dec[N];
 
 int mi[N], mx[N], k;
 
 bool cmpMAX(const int &a, const int &b){ return a>b; }
 bool cmpMIN(const int &a, const int &b){ return a<b; }
 
 void chk(int i, int &head, int &tail, node c[], bool cmp(const int &a, const int &b), int num)
 {                        //添加新節(jié)點(diǎn)到隊(duì)尾，并刪掉過(guò)期的頭節(jié)點(diǎn)
     while(tail >= head && cmp(c[tail].m, num)) tail--;
     c[++tail].m = num;
     c[tail].d = i;
     while(cmpMAX(i-c[head].d+1, k)) head++;//更新了一下head，如果保存的不在可視框內(nèi)，則不應(yīng)該考慮，否則wa
 }
 void solve()
 {
     int n, i, j, id=0, num;
     int head_I=0, tail_I=0, head_D=0, tail_D=0;
 
     scanf("%d%d", &n, &k);
     if(n>0 && k>=1)        //初始化化隊(duì)列里的第一個(gè)點(diǎn)
     {
         scanf("%d", &num);
         Inc[0].m = Dec[0].m = num;
         Inc[0].d = Dec[0].d = 0;
     }
     for(i=1; i<k; i++)    //初始化視窗中的點(diǎn): 加入隊(duì)列
     {
         scanf("%d", &num);
         chk(i, head_I, tail_I, Inc, cmpMIN, num);
         chk(i, head_D, tail_D, Dec, cmpMAX, num);
     }
     mi[id] = Inc[head_I].m;
     mx[id++] = Dec[head_D].m;
     for(; i<n; i++)        //添加并更新
     {
         scanf("%d", &num);
         chk(i, head_I, tail_I, Inc, cmpMIN, num);
         chk(i, head_D, tail_D, Dec, cmpMAX, num);
         mi[id] = Inc[head_I].m;
         mx[id++] = Dec[head_D].m;
     }
     printf("%d", mx[0]);
     for(i=1; i<id; i++) printf(" %d", mx[i]);
     printf("\n%d", mi[0]);
     for(i=1; i<id; i++) printf(" %d", mi[i]);
     printf("\n");
 }
 
 int main()
 {
     solve();
     return 0;
 }