// Source: https://usaco.guide/general/io

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

int main() {
    int m,n;cin>>m>>n;
    vector<int> v(n);
    for(int i = 0;i<n;i++){
        cin>>v[i];
    }
    vector<int> ans1,ans2;
    if(n==m){
        for(int i : v)ans1.push_back(i);
        for(int i : v)ans2.push_back(i);
    }
    else if(v[n-1]==n){
        for(int i = m-n+1; i<m+1;i++){
            ans1.push_back(i);
        }
    }
    else if(v[0]==m-n+1){
        for(int i = 1;i<=n;i++){
            ans2.push_back(i);
        }
    }
    if(ans1.empty()){
        int temp=0,neededval=m;
        for(int i = n-1;i>=0;i--){
            if(v[i]!=m){
                temp=i;
                break;
            }
            m--;
        }
        neededval=v[temp]+1;
        for(int i = 0;i<n;i++){
            if(i>=temp){
                ans1.push_back(neededval);
                neededval++;
            }
            else ans1.push_back(v[i]);
        }
    }
    if(ans2.empty()){
        int temp=0,neededval=m;
        for(int i = n-1;i>=0;i--){
            if(v[i]!=m){
                temp=i;
                break;
            }
            m--;
        }
        neededval=v[temp]-1;
        for(int i = 0;i<n;i++){
            if(i>=temp){
                ans2.push_back(neededval);
                neededval--;
            }
            else ans2.push_back(v[i]);
        }
    }
    for(int i : ans2)cout<<i<<' ';
    cout<<endl;
    for(int i : ans1)cout<<i<<' ';
    cout<<endl;
}