#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> ules(m + 2, 0);
    ules[m + 1] = n;
    for(int i = 1; i <= m; i++){
        cin >> ules[i];
    }

    int valtas = m;
    while(valtas > 0 && ules[valtas] - ules[valtas - 1] <= 1){
        valtas--;
    }

    //cout << valtas << "\n";
    if(valtas == 0){
        // legkisebb eset -> legnagyobbat kell kiirni
        for(int i = 1; i <= m; i++){
            cout << n - m + i << " ";
        }
    } else{
        for(int i = 1; i <= m; i++){
            if(valtas == i){
                cout << ules[i] - 1 << " ";
                for(int j = i + 1; j <= m; j++){
                    cout << n - m + j << " ";
                }
                break;
            } else{
                cout << ules[i] << " ";
            }
        }
    }

    cout << "\n";

    valtas = m;
    while(valtas > 0 && ules[valtas + 1] - ules[valtas] <= 1){
        valtas--;
    }

    //cout << valtas << "\n";

    if(valtas == 0){
        // legnagyobb eset -> legkisebbet kell kiirni
        for(int i = 1; i <= m; i++){
            cout << i << " ";
        }
    } else{
        for(int i = 1; i <= m; i++){
            if(valtas == i){
                cout << ules[i] + 1 << " ";
                for(int j = ules[i] + 2; i < m; j++){
                    cout << j << " ";
                    i++;
                }
            } else{
                cout << ules[i] << " ";
            }
        }
    }

    cout << "\n";
}