#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;
    }
    // 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
    int 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 - i - 1) << " ";
    }
    cout << '\n';
    // 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 (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';
}