#include <bits/stdc++.h>
#include <vector>
using namespace std;

int main(){
    int n, d;
    cin>>n>>d;
    vector<int>c(d+1);
    vector<int>eleje(d);
    vector<int>vege(d);
    int s=d-1;
    for(int i=1; i<=d; i++) eleje[i-1]=i;
    for(int i=n; i>=n-d+1; i--){
        vege[s]=i;
        s--;
    }
    for(int i=1; i<=d; i++){
        cin>>c[i]; 
    }
    int h=d-1;
    int akt=d;
   while(c[akt]-1<=c[h] && akt!=1){
        akt--;
        h--;
    }
    if(akt==1 && c[1]==1) for(int x : vege) cout<<x<<" ";
    else{
        bool v=false;
        for(int i=1; i<=d; i++){
            if(i==akt){
                cout<<c[i]-1<<" ";
            }
            else cout<<c[i]<<" ";
        }
    }
    cout<<endl;
    int akt2=-1;
    for(int i=1; i<d; i++) if(c[i]+1<c[i+1]) akt2=i;
    if(c[d]+1<=n) akt2=d;
    if(akt2!=-1){
        bool v=false;
        int g=0;
        for(int i=1; i<=d; i++){
            if(i==akt2){
                cout<<c[i]+1<<" ";
                v=true;
                g=c[i]+2;
            }
            else if(v){
                if(g<=n) cout<<g<<" ";
                else cout<<n<<" ";
                g++;
            }
            else cout<<c[i]<<" ";
        }
    }
    else{
        for(int x : eleje) cout<<x<<" ";
    }
}