#include <iostream>

using namespace std;

int n, k;
const int N = 1e6 + 10;
int a[N], q[N];    // q[] 存储下标

int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];

    int hh = 0, tt = -1;  // hh 队头， tt 队尾   
    // 队列 队尾入队 tt++ 队尾出队tt-- ，队头出队，hh--,队头入队 hh++;
    for(int i =0; i<n;i ++)
    {

        // 每次要把数插到里边去，   之前 先看看 
        // 1.  判断队头是否划出窗口  2. 是否 队尾元素 >= 当前插入的元素
        // 要是>= ，则队尾元素没有用，删掉。
        if(hh <= tt && q[hh] < i - k + 1)  
        {
            hh ++;
            //q[hh] 是下标，  要是不在[i-k+1,i] == [队头，队尾] 范围内， 则删掉 hh++即可
        }

        while( hh <= tt && a[ q[tt] ] >= a[i]) tt --;  // 队列中没用的元素删掉， 即 队尾--  使之有了单调性

        q[++tt] = i;  // 存储下标
        if(i >= k - 1)// 够了一个窗口了
            cout << a[q[hh]] <<   ' ' ; 

    }

    cout << endl;
    // 找最大值
     hh = 0, tt = -1;
    for(int i =0;i <n;i++)
    {
        if(hh <= tt && q[hh] < i - k + 1) hh++;
        while( hh <= tt && a[ q[tt]] <= a[i]) tt --; // find max 所以递减序列，每次删除没用的队尾元素
        q[++tt] = i;
        if(i >= k - 1)
            cout << a[q[hh]] << ' ' ;
    }

    return 0;
}

#include <iostream>

using namespace std;

const int N = 1e6 +10;

int a[N];
int q[N];

int n, k;  // 窗口k个数   [i - k + 1 , i]


int main(){
    cin >> n >> k;

    for(int i = 0; i<n;i++) cin >> a[i];

    int hh = 0, tt = -1;  // head  , tail     --出队  ++ 入队

    for(int i =0;i<n;i++)
    {
        if( hh <= tt && q[hh] < i - k + 1)  hh++;  // head 是否在窗口内， 没有则 + 1
        while( hh <= tt && a[ q[tt]] >= a[i])  // 队尾元素 >= 入队元素 则删除队尾元素，因为在找最小
             tt --;  //删除队尾元素， 因为下次入队 覆盖掉了

        q[++tt] = i; //存储入队元素的下标

        if(i >= k -1 ) cout << a[q[hh]] << ' ';
    }
    cout << endl;

    hh = 0, tt = -1;
    for(int i = 0; i<n;i++)
    {
        if(hh<=tt && q[hh] < i - k + 1) hh++;
        while(hh <= tt && a[q[tt]] <= a[i])  //find max
            tt --;  
        q[++tt]  = i;
        if(i >= k - 1) cout << a[q[hh]] << ' ';
    }





    return 0;
}