#include <iostream>

using namespace std;

int main()
{
    //ifstream cin("f.txt");
    int n, m, i;
    cin >> n >> m;
    int kov[m+2], el[m];
    for(i=0; i<m;i++)
    {
        cin >> kov[i+1];
        el[i] = kov[i+1];
    }
    kov[m+1] = n+1;
    kov[0] = n+1;
    for(i=m; i>-1; i--)if(kov[i]+1 < kov[i+1])break;
    if(i!=-1)
    {
        kov[i]++;
        for(i=i+1; i<=m; i++)kov[i] = kov[i-1]+1;
    }
    else for(i=1; i<=m; i++)kov[i] = i;

    for(i=m-1; i>-1; i--)if(el[i]-1 > el[i-1])break;
    if(i!=-1)
    {
        el[i]--;
        for(i=i+1; i<m; i++)el[i] = n-m+i+1;
    }
    else for(i=0; i<m; i++)el[i] = n-(m-i-1);
    for(i=0; i<m; i++)cout << el[i] << " ";
    cout << endl;
    for(i=1; i<=m; i++)cout << kov[i] << ' ';
    return 0;
}