#include <iostream>
using namespace std;

int n, m;

void write(int a[]){
    for(int i=0; i<m; i++){
        cout << a[i] << ' ';
    }
    cout << '\n';
}

void kovetkezo(int a[]){
    for(int i=m-1; i>=0; i--){
        if(a[i]<n-m+i+1){
            a[i]++;
            for(int j=i+1; j<m; j++){
                a[j]=a[i]+j-i;
            }
            return;
        }
    }
    for(int i=0; i<m; i++){
        a[i]=i+1;
    }
}

void elozo(int a[]){
    for(int i=m-1; i>0; i--){
        if(a[i]>a[i-1]+1){
            a[i]--;
            for(int j=i+1; j<m; j++){
                a[j]=n-m+j+1;
            }
            return;
        }
    }
    if(a[0]>1){
        a[0]--;
        for(int j=1; j<m; j++){
            a[j]=n-m+j+1;
        }
    }
    else{
        for(int i=0; i<m; i++){
            a[i]+=n-m;
        }
    }
}

int main(){
    cin >> n >> m;
    int a[m], b[m];
    for(int i=0; i<m; i++){
        cin >> a[i];
        b[i]=a[i];
    }
    elozo(a);
    kovetkezo(b);
    write(a);
    write(b);
}