#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const int maxN = 2e5 + 5;
const int MOD = 1e9 + 7;

string s, curr;
int n,m;

bool kisebb(string a) {
    for(int i = 0; i < m-1; i++) {
        if(a[i] > a[i+1]) return false;
    }

    return s.substr(0, m) > a.substr(0, m);
}

bool nagyobb(string a) {
    for(int i = 0; i < m-1; i++) {
        if(a[i] > a[i+1]) return false;
    }
    
    return s.substr(0, m) < a.substr(0, m);
}

int main() {



   InTheNameOfGod;
    
    
    cin >> n >> m;

    vector<bool> volt(n+1, 0);

    
    for(int i = 0; i < m; i++) {
        int x;
        cin >> x;
        volt[x] = 1;

        s.push_back('0' + x);
    }

    curr = s;
    for(int i = n; i > 0; i--) if(!volt[i]) curr.push_back('0' + i);

    while(!kisebb(curr)) prev_permutation(curr.begin(), curr.end());
    for(int i = 0; i < m; i++) cout << curr[i] << ' ';
    cout << "\n";
    curr = s;

    for(int i = 1; i <= n; i++) if(!volt[i]) curr.push_back('0' + i);

    while(!nagyobb(curr)) next_permutation(curr.begin(), curr.end());

    for(int i = 0; i < m; i++) cout << curr[i] << ' ';

    return 0;
}