#include <iostream>
#include <vector>

using namespace std;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<int> chairS(M);
    for (auto &e : chairS) {
        cin >> e;
    }
    int index;
    if (chairS[M - 1] == M) {
        index = -1;
    }
    else {
        // előző: csökkentjük a legutolsót, amit nem előz meg nála eggyel kisebb szám; a továbbiak a lehetséges értékek legvége lesznek
        index = M - 1;
        while (index > 0 && chairS[index] == chairS[index - 1] + 1) {
            --index;
        }
        for (int i = 0; i < index; i++) {
            cout << chairS[i] << " ";
        }
        cout << chairS[index] - 1 << " ";
    }
    for (int i = index + 1; i < M; i++) {
        cout << N - (M - 1 - i) << " ";
    }
    cout << '\n';
    if (chairS[0] == N - (M - 1)) {
        index = 0;
        chairS[0] = 1;
    }
    else {
        // következő: növeljük a legutolsót, amit még növelhetünk; a továbbiak közvetlenül utána következnek
        index = M - 1;
        while (index > 0 && chairS[index] == N - (M - 1) + index) {
            --index;
        }
        for (int i = 0; i < index; i++) {
            cout << chairS[i] << " ";
        }
        cout << ++chairS[index] << " ";
    }
    for (int i = index + 1; i < M; i++) {
        chairS[i] = chairS[i - 1] + 1;
        cout << chairS[i] << " ";
    }
    cout << '\n';
}