#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n,m,k;
vector<int>v;
int main()
{
    cin>>n>>m;
    v.resize(m+1);
    v[0]=0;
    for(int i=1 ; i<=m ; i++){
        int a;
        cin>>a;
        v[i]=a;
    }
    int i=m;
    bool b=1;
    while(i>=0 && b){
        for(int j=v[i]-1 ; j>=0 && b; j--){
            if(j<v[i] && j>v[i-1]){
                for(int p=1 ; p<=m ; p++){
                    if(p==i)cout<<j<<' ';
                    else cout<<v[p]<<' ';
                }
                b=0;
            }
        }
        i--;
    }
    cout<<endl;
    i=m;
    b=1;
    while(i>=0 && b){
        for(int j=v[i-1]+1 ; j<=n && b ; j++){
            if(j>v[i] && (i==m || j<v[i+1])){
                for(int p=1 ; p<=m ; p++){
                    if(p==i)cout<<j<<' ';
                    else cout<<v[p]<<' ';
                }
                b=0;
            }
        }
        i--;
    }




    return 0;
}