#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> van(n+1, 0);
    vector<int> v(n+1);
    for (int i=0; i<m; i++) {
        int x;
        cin >> x;
        van[x]++;
        v[i]=x;
    }

    int masik=-1, hol=m;
    while (masik==-1) {
        hol--;
        if (v[hol]>0 && van[v[hol]-1]==0) {
            masik=v[hol]-1;
        }
    }

    int b=0;
    while (b<hol) {
        cout << v[b]  << " ";
        b++;
    }
    cout << masik << " ";
    for (int i=n-(m-hol)+2; i<=n; i++) {
        cout << i << " ";
    }
    cout << "\n";

    int uj=-1, epp=m;
    while (uj==-1) {
        epp--;
        if (v[epp]<n && van[v[epp]+1]==0) {
            uj=v[epp]+1;
        }
    }
    int a=0;
    while (a<epp) {
        cout << v[a] << " ";
        a++;
    }
    for (int i=uj; i<uj+m-epp; i++) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}