#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];
    }

    if(m == 1){
        if(ules[1] - 1 > 0){
            cout << ules[1] - 1 << "\n";
        } else{
            cout << n << "\n";
        }

        if(ules[1] + 1 <= n){
            cout << ules[1] + 1 << "\n";
        } else{
            cout << "1\n";
        }
    } else{
        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";

        if(ules[m + 1] - ules[m] >= 1){
            valtas = m;
        } else{
            valtas = m - 1;
            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";
    }
}