#include <bits/stdc++.h>

using namespace std;

int main()
{
    //ifstream cin("in.txt");

    int n, m;
    cin >> n >> m;

    vector<int> v(m + 1, 0);

    for(int i = 1; i <= m; i++){
        cin >> v[i];
    }

    /// lefele:

    for(int i = m; i >= 0; i--){
        if(v[i] - 1 != v[i - 1]){
            int x = m - i + 1;

            int a = v[i] - 1;

            for(int j = 1; j < i; j++){
                cout << v[j] << " ";
            }

            for(int j = 0; j < x; j++){
                cout << a + j << " ";
            }

            break;
        }
        else if(i == 0){
            for(int j = n - m + 1; j <= n; j++){
                cout << j << " ";
            }
        }
    }

    cout << "\n";

    /// felfele:
    for(int i = m; i >= 0; i--){
        if(v[i] + 1 <= n - m + i){
            int x = n - m + i;

            for(int j = 1; j < i; j++){
                cout << v[j] << " ";
            }

            for(int j = x; j <= n; j++){
                cout << j << " ";
            }

            break;
        }
        else if(i == 0){
            for(int j = 1; j <= m; j++){
                cout << j << " ";
            }
        }
    }


    return 0;
}