#include <bits/stdc++.h>
using namespace std;

int n, m, a[102], b[102];

void csokkent(int k) {
    a[k]--;
    if(a[k] <= a[k-1]) {
        a[k] = a[k+1]-1;
        csokkent(k-1);
    }
}

void novel(int k) {
    if(b[k]+1 < b[k+1]) {
        b[k]++;
        for(int i = k+1; i <= m; i++) b[i] = b[i-1] + 1;
    } else {
        novel(k-1);
    }
}



int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> a[i]; 
        b[i] = a[i];
    }
    a[m+1] = n+1; b[m+1] = n+1;

    bool csaknem = true;
    for(int i = 1; i <= m; i++) if(a[i] != i) csaknem = false;

    if(csaknem) for(int i = m, j = n; i >= 1; i--, j--) a[i] = j;
    else csokkent(m);

    for(int i = 1; i <= m; i++) cout << a[i] << ' ';
    cout << endl;


    bool csak_nem = true;
    for(int i = m, j = n; i >= 1; i--, j--) if(b[i] != j) csak_nem = false;

    if(csak_nem) for(int i = 1; i <= m; i++) b[i] = i;
    else novel(m);

    for(int i = 1; i <= m; i++) cout << b[i] << ' ';

    return 0;
}