#include <iostream>
#include <queue>
#define ll long long

using namespace std;

vector <ll> x, y, z;
ll n, k;

bool jo(ll lep)
{
    if (y[lep - 1] <= y[lep] && y[lep] >= x[lep])
        return true;
    return false;
}

int main()
{
    cin >> n >> k;
    x.resize(k + 1);
    y.resize(k + 1);
    z.resize(k + 1);
    for (ll i = 1; i <= k; ++i)
    {
        cin >> x[i];
        y[i] = x[i];
        z[i] = x[i];
    }
    ll n1 = n, db = 0;
    for (ll i = k; i >= 1; --i)
    {
        if (y[i] == n1)
        {
            ++db;
            --n1;
        }
        else
        {
            ++y[i];
            for (ll j = i + 1; j <= k; ++j)
            {
                for (ll g = 1; g <= n; ++g)
                {
                    y[j] = g;
                    if (jo(j))
                        break;
                }
            }
            break;
        }
    }

    bool ok = false;
    for (ll i = 1; i <= k; ++i)
    {
        n1 = n - k + i;
        if (z[i] == n1)
        {
            z[i]--;
            ok = true;
            break;
        }
    }
    if (!ok)
    {
        z[1]--;
        for (ll i = 2; i <= k; ++i)
            z[i]++;
    }

    for (ll i = 1; i <= k; ++i)
        cout << z[i] << " ";

    cout << "\n";
    for (ll i = 1; i <= k; ++i)
        cout << y[i] << " ";

    return 0;
}
/*
6 4
1 2 4 6
*/