#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> van(n, 0);
    vector<int> v(n);
    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 (van[v[hol]-1]==0) {
            masik=v[hol]-1;
        }
    }

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

    int uj=-1, epp=m;
    while (uj==-1) {
        epp--;
        if (van[v[epp]+1]==0) {
            uj=v[epp]+1;
        }
    }

    int a=0;
    while (v[a]<uj-1) {
        cout << v[a] << " ";
        a++;
    }
    for (int i=uj; i<uj+m-epp; i++) {
        cout << i << " ";
    }



    return 0;
}