#include <iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n,m;
vector<int>nums;
vector<int>seged;

int main()
{
    cin>>n>>m;
    nums.resize(m);
    for(int i=0;i<m;i++) cin>>nums[i];
    if(m==1)
    {
        if(nums[0]==1) cout<<n<<endl<<2;
        if(nums[0]==n) cout<<n-1<<endl<<1;
        if(nums[0]<n && 1<nums[0]) cout<<nums[0]-1<<endl<<nums[0]+1;
        return 0;
    }

    if(nums[0]==n-m+1)
    {
        --nums[0];
        for(auto x:nums) cout<<x<<" ";
        cout<<endl;
        for(int i=1;i<=m;i++) cout<<i<<" ";
        return 0;
    }

    if(nums[m-1]==m)
    {
        for(int i=m;i>=1;i--) cout<<n-i+1<<" ";
        cout<<endl;
        ++nums[m-1];
        for(auto x:nums) cout<<x<<" ";
        return 0;
    }
    for(int i=m-1;i>=0;i--)
    {
        if(i!=0 && nums[i-1]==nums[i]-1) continue;
        for(int j=0;j<i;j++) cout<<nums[j]<<" ";
        cout<<nums[i]-1<<" ";
        for(int j=m-i-1;j>=1;j--) cout<<n-j+1<<" ";
        cout<<endl;
        break;
    }
    for(int i=m-1;i>=0;i--)
    {
        if(nums[i]==n -(m-i-1)) continue;
        for(int j=0;j<i;j++) cout<<nums[j]<<" ";
        for(int j=1;i+j<=m;j++) cout<<nums[i]+j<<" ";
        break;

    }


    return 0;
}