// Előző és következő ülés sorrend.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<int> x(m);
    for (int i = 0; i < m; i++)
        cin >> x[i];
    //kisebb
    bool ok = false;
    vector<int> og = x;
    for (int i = m-1; i >= 0; i--)
    {
        if ((i == 0 and x[i] > 1) or (i > 0 and x[i] - 1 > x[i - 1]))
        {
            ok = true;
            x[i]--;
            for (int y = i+1; y < m; y++)
            {
                x[y] = n-m+y+1;
            }
            break;
        }
    }
    if (!ok)
    {
        for (int y = 0; y < m; y++)
        {
            x[y] = n - m + y + 1;
        }
    }
    for (auto a : x)
        cout << a << " ";
    cout << endl;
    ok = false;
    for (int i = m - 1; i >= 0; i--)
    {
        if (og[i]<n-m+i+1)
        {
            ok = true;
            og[i]++;
            for (int y = i + 1; y < m; y++)
            {
                og[y] = og[y-1]+1;
            }
            break;
        }
    }
    if (!ok)
    {
        og[0] = 1;
        for (int y = 1; y < m; y++)
        {
            og[y] = og[y-1] + 1;
        }
    }
    for (auto a : og)
        cout << a << " ";

}