#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    vector <int> a;
    cin >> n >> m;
    a.resize(m);
    for(auto &i : a)
        cin >> i;
    int x;
    if(a[m - 1] != n){
        x = a[m - 1];
        a.pop_back();
        for(auto i : a)
            cout << i << " ";
        cout << x - 1 << endl;
        for(auto i : a)
            cout << i << " ";
        cout << x + 1;
    }
    else if(a[m - 1] == n){
        int ue = a[m - 2], u = a[m - 1];
        a.pop_back();
        a.pop_back();
        for(auto i : a)
            cout << i << " ";
        cout << ue << " " << u -- << endl;
        int poz = 0, db = 1;
        for(int i = m - 2; i > 1; i --){
            if(a[i] == n - db){
                db ++;
            }
            else{
                poz = i;
                break;
            }
        }
        for(int i = 0; i < poz; i ++)
            cout << a[i] << " ";
        int i = poz;
        int x = a[poz];
        while(i < m){
            x ++;
            cout << x << " ";
            i ++;
        }
    }
    return 0;
}