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

int main() {
	int n, m;
	cin>>n>>m;
	vector<int> v(m+2);
	v[0]=0; v[m+1]=n+1;
	for (int i=1;i<m+1;i++){
        cin >> v[i];
	}
	vector<int> z=v;
	bool van=false;
	for (int i=m;i>0;i--){
		if (v[i]-1!=v[i-1]){
			z[i]-=1;
			int nov=n;
			for (int j=m;j>i;j--){
				z[j]=nov;
				nov--;
			}
			for (int j=1;j<=m;j++) cout<<z[j]<<" ";
			van=true;
			break;
		}
	}
	if (!van){
    for (int i=n-m+1;i<=n;i++) cout<<i<<" ";
    }
    cout<<endl;
	van=false;
    for (int i=m;i>0;i--){
        if (v[i]+1!=v[i+1]){
            v[i]++;
			for (int j=i+1;j<m;j++){
				v[j]=v[j-1]+1;
			}
            for (int j=1;j<=m;j++) cout<<v[j]<<" ";
            van=true;
            break;
        }
    }
    if (!van){
    for (int i=1;i<=m;i++) cout<<i<<" ";
    }
}