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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (int i=0; i<m; i++){
        cin >> a[i];
    }
    int c=1;
    while (c < m && a[m-c-1] + 1 == a[m-c]){
        c++;
    }
    for (int i=0; i<m-c; i++){
        cout << a[i] << " ";
    }
    cout << (a[m-c]-1 ? a[m-c]-1 : n-m+1);
    for (int i=c-2; i>=0; i--){
        cout << " " << n-i;
    }
    cout << "\n";
    for (int i=0; i<m-c-1; i++){
        cout << a[i] << " ";
    }
    if (a.back() != n){
        if (c != m) cout << a[m-c-1] << " ";
        for (int i=m-c; i<m-1; i++){
            cout << a[i] << " ";
        }
        cout << a[m-1] + 1;
    }
    else{
        int x = 1;
        if (c != m){
            cout << a[m-c-1]+1 << " ";
            x = a[m-c-1]+2;
        }
        for (int i=x; i<x+c; i++){
            cout << i << " ";
        }
    }
}