#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 << '\n';
}

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

    egyesek--;
    for(int j=n-1; j>i; j--){
        if(egyesek>0){
            egyesek--;
            a[j]=1;
        }
        else{
            a[j]=0;
        }
    }
    write(a);
    return;
}

void kisebb(bool a[]){
    int i, egyesek=0, csere=0;
    if(a[n-1]) egyesek++;
    for(i=n-2; i>=0; i--){
        if(a[i]) egyesek++;
        if(a[i]==1&&a[i+1]==0){
            swap(a[i], a[i+1]);
            csere=1;
            break;
        }
    }
    egyesek--;
    for(int j=i+2; j<n; j++){
        if(egyesek>0){
            egyesek--;
            a[j]=1;
        }
        else{
            a[j]=0;
        }
    }
    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;
    }
    nagyobb(a);
    kisebb(b);
}