#include <iostream>
int n;

using namespace std;
void write(bool a[]){
    for(int i=0; i<n; i++){
        if(a[i]){
            cout << i+1 << ' ';
        }
        //cout << a[i] << ' ';
    }
    cout << '\n';
}

void nagyobb(bool a[]){
    int i=n-1, egyesek=-1;
    if(a[i]) egyesek++;
    i--;
    for(i=n-2; i>=0; i--){
        if(a[i]==1){
            egyesek++;
        }
        if(a[i]==0&&a[i+1]==1){
            swap(a[i], a[i+1]);
            break;
        }
    }
    for(int j=n-1; j>i; j--){
        if(egyesek){
            a[j]=1;
            egyesek--;
        }
        else{
            a[j]=0;
        }
    }
    write(a);
    return;
}

void kisebb(bool a[]){
    int i=n-1, nullasok=-1;
    if(!a[i]) nullasok++;
    i--;
    for(i=n-2; i>=0; i--){
        if(a[i]==0){
            nullasok++;
        }
        if(a[i]==1&&a[i+1]==0){
            swap(a[i], a[i+1]);
            break;
        }
    }
    for(int j=n-1; j>i; j--){
        if(nullasok){
            a[j]=0;
            nullasok--;
        }
        else{
            a[j]=1;
        }
    }
    write(a);
    return;
}




int main(){
    int m, x;
    cin >> n >> m;
    bool a[n], b[n];
    for(int i=0; i<n; i++){
        a[i]=0;
        b[i]=0;
    }
    while(m--){
        cin >> x;
        a[x-1]=1;
        b[x-1]=1;
    }
    //write(a);
    nagyobb(a);
    kisebb(b);
    //cout << "1 2 3 4\n";
}