#include <iostream>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    int a[m], x=-1, k;
    for(int i=0; i<m; i++)
    {
        cin >> a[i];
    }
    if(a[0]==n-m+1)
    {
        a[0]=max(n-m, 1);
        for(int i=0; i<m; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
        for(int i=1; i<=m; i++)
        {
            cout << i << " ";
        }
    }
    else if(a[m-1]==m)
    {
        for(int i=n-m+1; i<=n; i++)
        {
            cout << i << " ";
        }
        cout << endl;
        a[m-1]=min(m+1, n);
        for(int i=0; i<m; i++)
        {
            cout << a[i] << " ";
        }
    }
    else
    {
        for(int i=m-1; i>=0 and x==-1; i--)
        {
            if(a[i]-a[i-1]>1)
            {
                x=i;
            }
        }
        for(int i=0; i<m; i++)
        {
            if(i<x)
            {
                cout << a[i] << " ";
            }
            else if(i==x)
            {
                k=a[i]-1;
                cout << k << " ";
            }
            else
            {
                k++;
                cout << k << " ";
            }
        }
        cout << endl;
        x=-1;
        for(int i=m-1; i>=0 and x==-1; i--)
        {
            if(a[i]!=n and a[i+1]-a[i]>1)
            {
                x=i;
            }
        }
        for(int i=0; i<m; i++)
        {
            if(x==i)
            {
                cout << a[i]+1 << " ";
            }
            else
            {
                cout << a[i] << " ";
            }
        }
    }
    return 0;
}