#include <iostream>

using namespace std;

int main()
{
    int n, m, i, l1, l2;
    cin >> n >> m;
    int a[m+2];
    a[0] = 0;
    a[n+1] = 101;
    bool v1 = 0, v2=0;
    for(i=1; i<=m; i++)cin >> a[i];
    for(i=m; i>0; i--)
        if(!v1 && a[i]-1 > a[i-1])
        {
            v1 = 1;
            l1 = i;
        }
        else if(!v2 && a[i]+1 < a[i+1])
        {
            v2 = 1;
            l2 = i;
        }
    for(i=1; i<=m; i++)
        if(l1 == i)
            cout << a[l1]-1 << ' ';
        else cout << a[i] << ' ';
    cout << endl;
    for(i=1; i<=m; i++)
        if(l2 == i)
            cout << a[l2]+1 << ' ';
        else cout << a[i] << ' ';
    return 0;
}