#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(i == 0){
            for(int j = n - m + 1; j <= n; j++){
                cout << j << " ";
            }
        }
        else 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 = i; j <= m; j++){
                cout << a + j - i << " ";
            }

            break;
        }
    }

    cout << "\n";

    /// felfele:
    for(int i = m; i >= 0; i--){

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

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

            for(int j = x - 1; j <= x-1+m-i; j++){
                cout << j + 1 << " ";
            }

//            for(int j = i; j <= m; j++){
//                cout << x + j - i << " ";
//            }

            break;

        }
    }

    /*cout << "\n";

    for(int i = 1; i <= m; i++){
        cout << i << " ";
    }*/


    return 0;
}