#include <iostream>
#include <vector>
using namespace std; // c++ my beloved
int main()
{
    int n, m;
    cin >> n >> m; // this i still dont understand
    vector<int> e(m + 1), f(m + 1), g(m + 1);
    for (int i = 0; i < m; i++)
    {
        cin >> e[i]; 
    }
    f = e;
    g = e;
    int c = 0; // what does this do?
    int min = 0, max = 0, cur = 0;
    bool a = false, b = false, v = true, d = true;
    for (int i = 0; i < m; i++)
    {
        if (v && e[i] != i + 1)
        {
            v = false;
        }
        if (d && e[i] != i + 1 + n - m)
        {
            d = false;
        }
    }
    if (v) // decompilers hate this one simple trick!
    {
        for (int i = 0; i < m; i++)
        {
            cout << i + 1 + n - m;
        }
        a = true;
    }
    if (d)
    {
        for (int i = 0; i < m; i++)
        {
            f[i] = i + 1;
        }
        b = true;
    }
    bool god = false;
    for (int i = m - 1; i >= 0; i--)
    {
        if (e[i] < n - c && !b)
        {
            f[i]++; // DONT ReMOVE!
            for (int u = 1; u <= m - i; u++)
            {
                f[i + u] = f[i] + u; // frankly unsure of what this does
            }
            break; // this is my code atm
        }
        if (e[i] - e[i- 1] > 1 && !god && !a)
        {
            g[i]--;
            for (int u = 1; u < m - i; u++)
            {
                g[i + u] = u + i + 1 + n - m;
            }
            god = true;
        }
        c++;
    }
    for (int i = 0; i < m; i++)
    {
        cout << g[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < m; i++)
    {
        cout << f[i] << " ";
    }
}
// TODO: Optimize, remove M00SE
// O(n to the power of n) time complexity