#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

int n, m;
vector<bool> is;
vector<bool> ans;

void solve() {
    cin >> n >> m;
    is.assign(1 + n, false);
    for(int i = 0; i < m; i++) {
        int x;
        cin >> x;
        is[x] = true;
    }
    ans.assign(1 + n, false);
    bool ok = false;
    for(int i = 1; i <= m; i++) {
        if(!is[i]) {
            ok = true;
        }
    }
    if(!ok) {
        for(int i = n; i >= n - m + 1; i--) {
            ans[i] = true;
        }
    } else {
        int pos = 0;
        for(int i = n; i >= 1; i--) {
            if(is[i] && !is[i - 1]) {
                ans = is;
                ans[i] = false;
                ans[i - 1] = true;
                pos = i;
                break;
            }
        }
        int cnt = 0;
        for(int i = pos; i <= n; i++) {
            if(ans[i]) {
                cnt++;
            }
            ans[i] = 0;
        }
        for(int i = n; i >= n - cnt + 1; i--) {
            ans[i] = 1;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(ans[i]) {
            cout << i << " ";
        }
    }
    cout << "\n";
    ans.assign(1 + n, false);
    ok = false;
    for(int i = n; i >= n - m + 1; i--) {
        if(!is[i]) {
            ok = true;
        }
    }
    if(!ok) {
        for(int i = 1; i <= m; i++) {
            ans[i] = true;
        }
    } else {
        int pos = 0;
        for(int i = n; i >= 1; i--) {
            if(!is[i] && is[i - 1]) {
                ans = is;
                ans[i] = true;
                ans[i - 1] = false;
                pos = i + 1;
                break;
            }
        }
        int cnt = 0;
        for(int i = pos; i <= n; i++) {
            if(ans[i]) {
                cnt++;
            }
            ans[i] = 0;
        }
        for(int i = pos; i <= pos + cnt - 1; i++) {
            ans[i] = 1;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(ans[i]) {
            cout << i << " ";
        }
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}