#include <iostream>

using namespace std;

int main()
{
    int n,m,x,nv;
    cin>>n>>m;
    int u[m+1],e[m+1];
    nv=n;
    for(int i=1;i<=m;i++)
    {
        cin>>x;
        u[i]=x;
        e[i]=x;
    }
    //utana
    int hat=1;
    if(u[m]!=n)
    {
        u[m]++;
    }
    else
    {
        for(int i=m-1;i>=1;i--)
        {
            if(u[i]!=nv-hat)
            {
                u[i]++;
                for(int j=i+1;j<=m;j++)
                {
                    u[j]=u[j-1]+1;
                }
                break;
            }
            else
            {
                continue;
            }
            hat++;
        }
    }

    ///elotte
    hat=0;
    bool ok=false;
    for(int i=m;i>=2;i--)
    {
        if(e[i]>=e[i-1]+2)
        {
            e[i]--;
            ok=true;
            for(int j=m;j>=i+1;j--)
            {
                e[j]=nv-hat;
                hat++;
            }
            break;
        }
       else
       {
           continue;
       }
    }
    if(!ok)
    {
        e[1]--;
        for(int j=m;j>=2;j--)
        {
            e[j]=nv-hat;
            hat++;
        }
    }
    for(int k=1;k<=m;k++)
    {
        cout<<e[k]<<" ";
    }
    cout<<endl;
    for(int k=1;k<=m;k++)
    {
        cout<<u[k]<<" ";
    }
    return 0;
}