#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int m,n;
    cin>>n>>m;
    vector<int> a(m+2);
    for(int i=1;i<=m;i++)
        {
        cin>>a[i];
        }
    a[0]=0;
    a[m+1]=n+1;
    int i=m;
    while(i>0 && a[i-1]+1==a[i])i--;
    for(int j=1;j<i;j++)cout<<a[j]<<" ";
    if(i!=0)cout<<a[i]-1<<" ";
    for(int j=i+1;j<=m;j++)cout<<n-m+j<<" ";
    cout<<"\n";
    i=m;
    while(i>0 && a[i+1]-1==a[i])i--;
    for(int j=1;j<i;j++)cout<<a[j]<<" ";
    if(i!=0)cout<<a[i]+1<<" ";
    for(int j=i+1;j<=m;j++){cout<<a[i-1]+1<<" ";a[i]=a[i-1]+1;}
    return 0;
}