#include <iostream>

using namespace std;

int main()
{
    int n, m, i;
    cin >> n >> m;
    int kov[m+1], el[m];
    for(i=0; i<m;i++)
    {
        cin >> kov[i];
        el[i] = kov[i];
    }
    kov[m] = n+1;
    for(i=m-1; i>=0; i--)if(kov[i]+1 < kov[i+1])break;
    kov[i]++;
    for(i=i+1; i<m; i++)kov[i] = kov[i-1]+1;
    for(i=m-1; i>0; i--)if(el[i]-1 > el[i-1])break;
    el[i]--;
    for(i=i+1; i<m; i++)el[i] = n-(m-i)+1;
    for(i=0; i<m; i++)cout << el[i] << " ";
    cout << endl;
    for(i=0; i<m; i++)cout << kov[i] << ' ';
    return 0;
}