#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n,m,x;
    cin>>n>>m;
    vector<int> ules(m+1,0), ulesn(m+1,0);
    ulesn.push_back(2147483647);
    ules[0]=0;
    for(int i=1; i<=m; i++)
    {
        cin>>ules[i];
        ulesn[i]=ules[i];
    }
    x=m;
    bool t=false;
    while(x>=1 && !t)
    {
        if(ules[x]>ules[x-1]+1)
        {
            ules[x]--;
            t=true;
        }
        else x--;
    }
    if(t)for(int i=1; i<=m; i++)cout<<ules[i]<<" ";
    else for(int i=n-m+1; i<=n; i++)cout<<i<<" ";
    cout<<endl;
    x=m;
    t=false;
    while(x>=1 && !t)
    {
        if(ulesn[x]<n && ulesn[x]+1<ulesn[x+1])
        {
                ulesn[x]++;
                t=true;
        }
        else x--;
    }
    if(t)for(int i=1; i<=m; i++)cout<<ulesn[i]<<" ";
    else for(int i=1; i<=m; i++)cout<<i<<" ";
    return 0;
}